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,

5 responses to “fibonacci series in python (Time complexity:O(1))”

  1. Aravind Emmadishetty says:

    But, this series produces wrong results for higher numbers.
    example:
    fib(100) is 354224848179261915075
    but the result produced by the above program is 354224848179263111168 which is same upto some extent except the last seven digits.
    for larger numbers such as 1000 the whole Answer may change.

  2. Prakash Raj says:

    Actually, in the above program I have used a round function which round-off the value after computing each term of the series which is well suited for the small number but in case of larger number value will change due to round function.
    you can use the following code for a large number :
    for example fib(10000)

    fib_list=[0,1]
    for i in range(2,10000):
    fib_list.append(fib_list[i-1]+fib_list[i-2])
    print(fib_list[len(fib_list)-1])

  3. Aravind Emmadishetty says:

    The iterative method in the above program deals with list which stores values upto fib(10000). Lot of space is used.
    Here’s my simple program of O(n) using iterative method.

    def fib(x):
    k1=0;k2=1
    l=0
    for i in range(x-1):
    l=k1+k2
    k1,k2=k2,l
    return l
    for i in range(10000):
    print(fib(i))

  4. Prakash Raj says:

    instead of a list, you can also use the only variable no problem at all.
    In your code, I show that everything is fine but at initially it printed like this 0 0 1 2 3 5 8……… instead of 0 1 1 2 3 5…

  5. Aravind Emmadishetty says:

    Thanks for point that. Just replacing ” x-1 ” with ” x ” will resolve that issue.

Leave a Reply

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