What is the Big O complexity of this program...I got O(2^n) but i am not able to find correct answer

Question

def fib(n):
    if n==0 or n==1:
        return n
    else:
        return fib(n-1)+fib(n-2)

n = int(input())
for val in range(n):
    print(fib(val))

#I did some calculation and got O(n^2)but I dont know the correct answer

Answer 1

A different argument:

Your algorithm recurses until it "bottoms out" at fib(1) which returns 1.

So you are getting the fibonacci number by doing (fibonacci number) calls and adding the 1s.

So fib(n) is O(fib(n)).

Binet's Fibonacci formula can be written as fib(n) == int(0.5 + (phi ** n) / (5 ** 0.5)) where phi is the Golden Ratio, 1.6180339...

Stripping constants, you get O(phi ** n) which reduces to O(2 ** n).

Now, fib(n) is actually a bit more than O(fib(n)), because you also make a bunch of calls to fib(0) which returns 0 - thus it adds to the number of calls but not the sum.

It turns out that when computing fib(n), you make fib(n - 1) calls to fib(0) (challenge: write a function to prove this!).

So fib(n) is actually O(fib(n) + fib(n - 1)) which is O(fib(n + 1)) which is O(phi ** (n + 1)), which still reduces to O(2 ** n).