Fibonacci sequence. Time Complexity

Question

First of all - yes, I know that there are a ton kind of similar questions about this but I still don't get it.

So the Big-O Notation of this code is O(2^n)

 public static int Fibonacci(int n)
    {
        if (n <= 1)
            return n;
        else
            return Fibonacci(n - 1) + Fibonacci(n - 2);
    }

And even though if I run it using let's say 6 , function is getting called 25 times as you can see in this picture:

Fibonacci Shouldn't it be 64 because of O(2^6) = 64 ?

That code is wrong, it gives `Fib(0)` to be `0`, when it should be `1` — Alexander, Apr 09 '17 at 17:30
@Alexander That depends if you refer to `fib(0) = fib(1) = 1` or `fib(1) = fib(2) = 1`, both are fine - only depends where you start indexing from. — amit, Apr 09 '17 at 17:31
Also: `O(2^(n - 1))` is still `O(2^(n))`. An offset by a constant is trumped by `n` as `n` approaches infinity. — Alexander, Apr 09 '17 at 17:31

score 1 · Accepted Answer · edited May 23 '17 at 11:54

1

Few issues with the logic here:

Big O notation is only giving upper asymptotic bound, not a tight bound, that's what big Theta is for.
Fibonacci is actually Theta(phi^n), if you are looking for tighter bound (where phi is the "golden ration", phi ~= 1.618.
When talking about asymptotic notation, there isn't much point in talking about low numbers, and neglecting the constants - since they are omitted for the asymptotic complexity (This is not the case here though).

In here, the issue is fibonacci is indeed O(2^n), but that bound is not tight, so the actual number of calls is going to be lower than the estimated one (for sufficiently large n, onwards).

edited May 23 '17 at 11:54

Community

1
1

answered Apr 09 '17 at 17:30

amit

175,853
27
231
333

Thanks, I have a better understanding now. Could you please take a look at this - [Fibonacci](http://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence) There is an answer on this thread by one person who "draws" pyramids to visually show how to get O(2^n). He uses the same algorithm and starts on `Fib(6)` and somehow manages to get 64. That's a part I don't understand. Could you please comment on that? – Daniel Apr 09 '17 at 17:41
@Daniel There is already a comment by Avik there, saying the pyramid is wrong, for `F(3)` is being called 3 times, not 4: F(6) = F(5) + F(4) = F(4) + `F(3) + F(3) + F(2) = F(3) + F(2) + F(3) + F(3) + F(2)`. (The same mistake then follows in the next rows as well). – amit Apr 09 '17 at 17:46

Fibonacci sequence. Time Complexity

1 Answers1