Time complexity for all Fibonacci numbers from 0 to n

Question

I was calculating the time complexity of this code that prints all Fibonacci numbers from 0 to n. According to what I calculated, the fib() method takes O(2^n) and since it is being called i number of times, so it came out to be O(n*2^n). However, the book says it is O(2^n). Can anyone explain why the time complexity here will be O(2^n)?

Here is the code:

void allFib(int n){
    for(int i = 0 ; i < n ; i++){
        System.out.println(i + ": " + fib(i));
    }
}

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

Possible duplicate of [Computational complexity of Fibonacci Sequence](https://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence) — Am_I_Helpful, Jul 29 '18 at 02:36
@Am_I_Helpful please read the question carefully before marking it duplicate. The content in the link you provided is not the answer to my question. — Yuva K, Jul 29 '18 at 02:43
When calculating `fib(n)`, you already got all the results for `fib(n -1)` to `fib(1)`. So calculate `fib(n)` has the same complexity as calculating all of them. But your `allFib` function is different as it doesn't save previous `fib(n-1)` and `fib(n-2)` to calculate `fib(n)`. So `allFib` has time complexity of O(n*2^n). — shaun shia, Jul 29 '18 at 03:14
@shaunshia that is what my answer was, but the book says it is O(n*2^n) and it is not any book, it Cracking the Coding Interview by G.L. Mcdowell. — Yuva K, Jul 29 '18 at 03:41
Possible duplicate of [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Richardissimo, Jul 29 '18 at 04:44

score 4 · Answer 1 · answered Dec 27 '19 at 11:07

I've figured it out my own way to understand the book's solution, hope it helps those who are still struggling.

Imagine we now call allFib(n).

Since we have a for loop from 0 to n, the following function will be called:

i = 0, call fib(0)
i = 1, call fib(1)
i = 2, call fib(2)
...
i = n-1, call fib(n-1)

As discussed before fib(n) will take O(2^n) = 2^n steps Therefore,

i = 0, call fib(0) takes 2^0 steps
i = 1, call fib(1) takes 2^1 steps
i = 2, call fib(2) takes 2^2 steps
...
i = n-1, call fib(n-1) takes 2^(n-1) steps

Thus, the runtime of allFib(n) will be

2^0 + 2^1 + 2^2 + ... + 2^(n-1). *

Follow the sum of powers of 2 formula we have:

* = 2^(n-1+1) - 1 = 2^n - 1.

Thus it is O(2^n)

score 1 · Answer 2 · answered Jul 29 '18 at 04:51

1

I finally got my answer from my professor and I'll post it here:

According to him: you should not just simply look the for loop iterating from 0 to n, but you must find what are the actual computations by calculating the steps.

fib(1) takes 2^1 steps

fib(2) takes 2^2 steps

fib(3) takes 2^3 steps

..........

fib(n) takes 2^n steps

now adding these:

2^1 + 2^2 + 2^3 + ........+ 2^n = 2^n+1

and ignoring the constant, it is 2^n, hence the time complexity is O(2^n).

answered Jul 29 '18 at 04:51

Yuva K

131
2
10

2

To me this merely explains time complexity for `fib(n)` itself. And I do understand the reasoning it must be `2^n`. But still. `fib(n)` is found within a `for` loop. Which means fib(n) is called n times. I fail to understand why it's not `n * 2^n` – newsha Sep 06 '18 at 10:26
3

You seemed to have said the same thing what book has said. – gaurawerma Oct 19 '18 at 09:59

Time complexity for all Fibonacci numbers from 0 to n

2 Answers2

Linked