fibonacci series in python (Time complexity:O(1))

In this tutorial, we gonna show you optimize and easy way of printing Fibonacci series in Python.

Print Fibonacci series in Python

In simple meaning, the Fibonacci number is the number which obtained by addition of two previous consecutive
number. for example
0,1,1,2,3,5,8,13,21,34,55,89,144,………
In mathematics Fibonacci series is obtained by expression

Fn=Fn-1+Fn-2.

where the initial condition is given as:

F0=0 and F1=1.

After solving Fn=Fn-1+Fn-2 expression you will get a formula by which you can calculate nth term of Fibonacci series.



Fn={[(√5+1)/2]∧n}/√5.

At first import math package to use the in-built function like pow, sqrt, etc.

Python program to find Fibonacci sequence

import math

Create a function which calculates and return nth term of Fibonacci series:

def fib(x):
    #we used formula for finding nth term of fibonacci series.
    # Formula Fn={[(√5+1)/2]∧n}/√5.
    #Above formula you wil get after solving Fn=Fn-1+Fn-2 on given initial condition F[0]=0,F[1]=1.
    n=(math.sqrt(5)+1)/2
    #round function used to round the value Ex:- round(3.2)=3 ,round(3.6)=4
    return round(math.pow(n,x)/math.sqrt(5))

User input: Enter the number of terms which are going to print:

n=int(input("enter the no of terms"))

Now the whole program to print Fibonacci series:

import math
def fib(x):
    #we used formula for finding nth term of fibonacci series.
    # Formula Fn={[(√5+1)/2]∧n}/√5.
    #Above formula you wil get after solving Fn=Fn-1+Fn-2 on given initial condition F[0]=0,F[1]=1.
    n=(math.sqrt(5)+1)/2
    #round function used to round the value Ex:- round(3.2)=3 ,round(3.6)=4
    return round(math.pow(n,x)/math.sqrt(5))
n=int(input("enter the no of terms "))
for i in range(n):
    #end used for printing in single line
    print(fib(i),end=" ")

Output:

enter the no of terms13
0 1 1 2 3 5 8 13 21 34 55 89 144

Except for the above method, there are various method to solve this problem like

  • recursion
  • by simply addition
  • by dynamic programming

But optimized one is above given solution (by Formula) :

Time Complexity:O(1)
Space complexity:O(1)

You may also read,

Leave a Reply

Your email address will not be published. Required fields are marked *