1

The same question has been asked here: Time complexity for all Fibonacci numbers from 0 to n, but I fail to understand the answer provided.

The following code prints all Fibonacci numbers from 0 to n. What is the time complexity?

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);
}

I don't understand why the time complexity is O(2^n) rather than O(n * 2^n). It has been said that:

fib(1) takes 2^1 steps

...

fib(n) takes 2^n steps

I can't see how this is true, since fib(1) immediately returns 1 based on the else statement, so it should take 1 step. Even if this statement were true, I still can't understand how the time complexity is only O(2^n).

Warren Crasta
  • 478
  • 8
  • 20
  • 1
    Simply put, your formula of O(n × 2^n) would be correct if you had _n_ steps of O(2^n) but you don't have that. You have _n_ steps, alright, but only the last of them is of O(2^n). The one before the last is of O(2^(n-1)), the one before that is of O(2^(n-2)), etc. All of them are way smaller than the last one, so they all can be dropped (within O()), and the O(2^n) remains as the fastest-growing term. – Alfe Apr 08 '19 at 09:12

1 Answers1

1

For the written program the if the time complexity of fib(n) be T1(n), total time complexity of the program is T(n) = sum_{i=0}^{n-1} T1(i). Now try to compute T1(i). By the definition of the fib function, T1(i) = T1(i-1) + T2(i-2) + 2 and T1(0) = 1 (one comparison) and T1(1) = 2 (two comparisons).

From the well-known previous analysis, we know that T1(i) = Theta(2^i). Hence, T(n) = Theta(sum_{i=1}^{n-1} 2^i) = Theta(2^n - 1) = Theta(2^n).

OmG
  • 18,337
  • 10
  • 57
  • 90