[byrandomby1]

Why is the time complexity of the Fibonacci recursive sequence O(2^n)?

int fib(int n)
    {
    if (n <= 2) return 1
    else return fib(n-1) + fib(n-2)
    }

How do I differentiate between O(2^n) and O(n^2)?

If there is a recursive function

int fib(int n)
    {
    if (n <= 3) return 1
    else return fib(n-1) + fib(n-2) + fib(n-3)
    }

would the time complexity be O(3^n)?

[macosxnerd101]

The Fibonacci sequence is O(2^n). You can prove it mathematically. Remember the definition of Big-O: f(n) is O(g(n)) iff there exist constants C and k (positive integers) such that |f(x)| <= C*|g(x)| for all x >= k.

So we know that Fibonacci is f(n) = f(n-1) + f(n-2), f(0) = 0, f(1) = 1. Let g(n) = 2^n. Now prove inductively that f(n) <= g(n) starting at some x. Then solve for C.

I have a Big-O proofs tutorial you may find helpful.

[sepp2k]

macosxnerd101, on 06 October 2012 - 08:11 PM, said:

The Fibonacci sequence is O(2^n).

Note that this does not automatically imply that the cost of calculating the Fibonacci sequence is also in O(2^n) (and more importantly Theta(2^n)) (and in fact there are many ways of calculating it that are O(n)). So you still need to show that this particular way of calculating the sequence takes a number of steps proportional to fib(n).

[macosxnerd101]

That's a good point. Actually solving the recurrence relation mathematically would allow you to find the first n Fibonacci numbers in O(n) time. This particular solution is O(2^n).

[mojo666]

Quote

Why is the time complexity of the Fibonacci recursive sequence O(2^n)?

The reason the recursive variation is O(2^n) is because it does a lot of redundant calculations. For example, you need to calculate fib(n-1) + fib(n-2). In order to find fib(n-1), you need to calculate fib(n-2)+fib(n-3). So, already all the work that goes into calculating fib(n-2) is done twice. To understand it conceptually, I suggest you pick a few numbers for n and draw out the corresponding recursive calls. You will see that fib(1) and fib(2) get called about O(2^n) times. To show it formally, you should try what Mac suggested.

Quote

How do I differentiate between O(2^n) and O(n^2)?

An easy way to conceptualize 2^n is thinking "if I increase n by one, then I just doubled the runtime." That means if you increase n by 2 then you doubled the already doubled runtime and so on. To conceptualize O(n^2), if you increase n by 1, then you roughly added 2*n units of time to the runtime.

Quote

would the time complexity be O(3^n)?

Yes.