Table of Content
- What is the Fibonacci Sequence?
- How to Solve Fibonacci Sequence in Python
- How to Determine the Big O Complexity of Fibonacci Sequence
- Wrap Off
From this section of the series, we will dive into solving our first algorithms.
In this lesson, you will learn about the Fibonacci sequence, how to solve it using loops in Python language and calculate the big O complexity.
What is the Fibonacci Sequence?
The Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones.
It is a concept used in mathematics, but we will focus on programming and algorithmic implementation.
The first two numbers in the sequence are 0 and 1.
For example:
Fibonacci of 2 is 0, 1.
Fibonacci of 3 is 0, 1, 1. This is because the third number is the sum of the previous two numbers.
Fibonacci of 7 is 0,1,1,2,3,5,8.
Let's represent the above as a function and output:
fib(2) # 0,1
fib(3) # 0,1,1
fib(7) # 0,1,1,2,3,5,8
How to Solve Fibonacci Sequence in Python
Here is a typical problem statement for the Fibonacci sequence.
Given a number n find the first n elements of the Fibonacci sequence.
Alright, let's solve the problem together.
We will begin by defining the function named fib in Python.
The function will have one parameter n, which denotes how many numbers in the sequence we have to display.
For example, calling the function with n equal to 2, 3, and 7 should return an array of Fibonacci sequence with the same length.
def fib(n):
...
Now, what do we know about the Fibonacci sequence? We know that the first two numbers are 0 and 1.
Let's create a variable called “fibs” and initialize it with a list of two numbers: 0 and 1.
def fib(n):
fibs = [0,1]
Next, we need to populate the remaining elements from the third element until we get to n while satisfying the condition that every number should be the sum of the previous two numbers,
To populate the remaining elements programmatically, we use a for loop that starts at an index equal to 2.
Since we already have elements with an index equal to 0 and index equal to 1, we iterate until we have n elements in the array.
def fib(n):
fibs = [0,1]
for i in range(2, n+1):
fibs.append(fibs[i-1] + fibs[i-2])
Lastly, we return the array.
def fib(n):
fibs = [0,1]
for i in range(2, n+1):
fibs.append(fibs[i-1] + fibs[i-2])
return fibs
That pretty much is our implementation of the Fibonacci sequence in Python. Let's verify by running the code.
print(fib(2))
print(fib(3))
print(fib(7))
You should get the output corresponding to each function we call.
0,1
0,1,1
0,1,1,2,3,5,8
How to Determine the Big O Complexity of Fibonacci Sequence
Next, we will determine the big O of our Fibonacci function in Python.
To determine the big O complexity of the function, you can either determine how many times each step is executed and then approximate the big O, as we have learned before, or you can use the rule of thumb we gave in this section as a shortcut to speed up the process.
Let's determine the big O together.
Our function contains one for loop, which repeats n times.
The line fibs = [0,1] runs once.
The line return fibs will also run once.
The big O will be = O(n + 1 + 1) = O(n + 2) = O(n)
From our guidelines in previous lessons, it is pretty evident that the big O complexity is linear time complexity.
So, big O is equal to O(n) as the value of n increases, the number of times line 4 executes also increases.
Wrap Off
That concludes our first algorithm in this course.
Hopefully, you're now able to get into the mindset of problem-solving and what to expect from each lesson in this course.
In the next lessons, we will look at more common math algorithms and progress to harder once in later lessons.
If you learned from this tutorial, or it helped you in any way, please consider sharing and subscribing to our newsletter.
Please share this post and for more insightful posts on business, technology, engineering, history, and marketing, subscribe to our newsletter.