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?

Then you should have realised that a sentence like "The time complexity of Fibonacci is O(2^n)" doesn't make sense. you can only say "the following implementation has a complexity of..." — Karoly Horvath, Feb 20 '14 at 15:24
I would take care of that next time. Now can you please answer that. Although it was not asked correctly but I think you have understood what I want to ask. — Haseeb Jadoon, Feb 20 '14 at 15:29
@Korhner.. If we consider that as a tree then the depth would be 'n' and cost at each step is O(1) therefore its O(n). Correct me if I am wrong — Haseeb Jadoon, Feb 20 '14 at 15:41
note: exponential growth is clearly visible from the recurrence relation: fibonacci(n)=fibonacci(n-1)+fibonacci(n-2) . to solve the problem, some subproblems(fibonacci(n-2)) have to be calculated multiple times. — Karoly Horvath, Feb 21 '14 at 01:17

score 3 · Answer 1 · edited May 23 '17 at 12:02

3

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

enter image description here

edited May 23 '17 at 12:02

Community

1
1

answered Feb 20 '14 at 15:31

Déjà vu

28,223
6
72
100

Then why is the complexity of the algorithm to traverse binary tree is O(n) rather than O(2^n)? – Haseeb Jadoon Feb 20 '14 at 15:51
The complexity to traverse a binary tree *made of n* nodes is O(n). The complexity to traverse a tree similar to the one generated by Fibonacci, ie more like ~2^n is obviously O(2^n). – Déjà vu Feb 20 '14 at 15:53
This answer doesn't answer the question at all, and the diagram doesn't seem to help. – anatolyg Feb 20 '14 at 15:53
1

Because your fibonacci algorithm does not use memoization and it calculates the same value more than once while tree traversal visits each node only once. – Adam Arold Feb 20 '14 at 15:53
@ring0 `The complexity to traverse a tree similar to the one generated by Fibonacci, ie more like ~2^n is obviously O(2^n)` this depends on what you call `n`. The number of nodes or the parameter which you use to call `fibonacci()`. – Adam Arold Feb 20 '14 at 15:55
@anatolyg OP's friend suggests the modified Fibonacci as an algorithm to get a O(3^n) time complexity - this answer shows that indeed it has that complexity. – Déjà vu Feb 20 '14 at 15:57
@AdamArold Indeed, when providing *n* as Fibonacci parameter. – Déjà vu Feb 20 '14 at 15:58
@ring0 There is a logical flaw here: you can't say that the tree traversal of the nodes generated has the complexity of O(2^n) in the context of the tree traversal algorithm because in that context `n` becomes the number of nodes of that tree. This is like local scope. The outer `n` gets shadowed by the inner `n` (tree traversal context). – Adam Arold Feb 20 '14 at 16:01

score 3 · Accepted Answer · edited May 23 '17 at 12:02

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

Then why is the complexity of the algorithm to traversal of binary tree is O(n) rather than O(2^n)? — Haseeb Jadoon, Feb 20 '14 at 15:46

Exponential Time complexity

2 Answers2