Exponential Time complexity

Question

The time complexity of Fibonacci is O(2^n) What if I want to get time complexity of 3^n?

According to my friend the time complexity of fibonacci is O(2^n) due to following step:-

return fibonacci(n-1)+fibonacci(n-2)

Additionally he said that it will become O(3^n) if we write:-

return fibonacci(n-1)+fibonacci(n-2)+fibonacci(n-3)

Can somebody tell why is this so?

According to him it's because we are calling Fibonacci function twice at each step that's why it's O(2^n). If so, then the complexity of the following code should be O(k^k) but as per my knowledge it's O(n)

void permute(int k,int size) {  
    // some base case    
    for (i=k-1;i>=0;i--)          
    permute(k-1,size);  
    return; 
}

His logics seems rubbish to me. To me it's 2^n due to the combine cost. Same goes for the Binary tree traversal cost it's O(n) despite of function calling itself twice at each step.

Can somebody tell me who is wrong amongst us and what's the actual logic?

Answer 1

Actually O(2^n) is overshooting it a bit (but still correct, since big-O is an upper bound), it's more like ~θ(1.6^n).

Try to picture a recursion tree. Every node splits into 2, and the depth of the tree is n, so it ends up as about O(2^n).

Similarly, the O(3^n) example, every node splits into 3, and the depth is still n.

But for O(3^n), I'd rather recommend something like this:

someFunction(n)
  if (n == 0)
    return 1
  return someFunction(n-1) + someFunction(n-1) + someFunction(n-1)

Of course this can trivially converted to O(n) by changing the last return statement to:

return 3*someFunction(n-1)

But that's not really the point (one could also calculate the n-th Fibonacci number in O(n)).

Now it's quite easy to evaluate.

There is 1 call for n, 3 for n-1, 3*3 for n-2, 3*3*3 for n-3, etc.

It follows trivially that the running time would be O(3^n).

---

For the permute function:

Since you're passing k-1 to the recursive call (not i), you have 1 call for k, k-1 for k-1, (k-1)(k-2) for k-2, (k-1)(k-2)(k-3) for k-3, etc.

So that looks like O((k-1)!).

---

If you were to instead pass i, you'd have 1 call for k, 1 for k-1, 1+1=2 for k-2, 1+1+2=4 for k-3, 1+1+2+4=8 for k-4, 16 for k-5, etc.

So that looks like O(2^(k-1)).

---

Binary tree traversal takes O(n), but n isn't the height of the binary tree, it's the number of nodes. In the Fibonacci example, n is the height. If we were to consider how long traversing a balanced binary tree will take based on the height, we'd also end up with O(2^height), which, from some basic mathematics, ends up as O(n).

Answer 2

This previous answer should persuade you about Fibonacci's sequence algorithm time complexity.

Then, based on that same answer principle, your new sequence algorithm can be represented as

T(n) 
= T(n-1) + T(n-2) + T(n-3) 
= ( T(n-2)+T(n-3)+T(n-4) )+( T(n-3)+T(n-4)+T(n-5) )+( T(n-4)+T(n-5)+T(n-6) )
= ...

you see that each node creates 3 new nodes. That algorithm complexity becomes O(3^n)

Image from Wolfram: (consider the nodes 13 to 37 to be continued below, since the bottom of the tree is not "flat", as the first level "n-3" node will complete before "n-2", completing before "n-1", etc...)