How to Solve Fibonacci Sequence in Python and Find the Big O Complexity

Learn about the Fibonacci sequence and how to determine the big O complexity

Picture of Nsikak Imoh, author of Macsika Blog
White background with the text How to Solve Fibonacci Sequence in Python and Find the Big O Complexity
White background with the text How to Solve Fibonacci Sequence in Python and Find the Big O Complexity

Table of Content

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):
Highlighted code sample.

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]
Highlighted code sample.

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])
Highlighted code sample.

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
Highlighted code sample.

That pretty much is our implementation of the Fibonacci sequence in Python. Let's verify by running the code.

Highlighted code sample.

You should get the output corresponding to each function we call.

Highlighted code sample.

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.

Next Tutorial — How to Find the Factorial of a Number in Python and the Big O ComplexityGet the Complete Code of Algorithms: Baby-Steps to Complete Mastery on Github.

Connect with me.

Need an engineer on your team to grease an idea, build a great product, grow a business or just sip tea and share a laugh?