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
– Alexander, Commented Apr 9, 2017 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
– amit, Commented Apr 9, 2017 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
– Alexander, Commented Apr 9, 2017 at 17:31

Community · Accepted Answer · 2017-05-23 11:54:04Z

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, 2017 at 11:54

CommunityBot

11 silver badge

answered Apr 9, 2017 at 17:30

amit

179k27 gold badges245 silver badges348 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Daniel Over a year ago

Thanks, I have a better understanding now. Could you please take a look at this - Fibonacci 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?

amit Over a year ago

@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).

Collectives™ on Stack Overflow

Fibonacci sequence. Time Complexity

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related