CODEWITHSUNDEEP
javascripttime-complexity
rogawiv352
rogawiv352

Reputation: 15

Recursive Functions Runtime 2^n - 1

I have the following function fn(n).

function fn(n) {
  if (n < 0) return 0;
  if (n < 2) return n;

  return fn(n - 1) + fn(n - 2);
}

I understand how this code works, but don't how to calculate time complexity for it.

Let’s do some examples:

For n = 3, you have 5 function calls. First fn(3), which in turn calls fn(2) and fn(1) and so on.

For n = 4, you have 9 function calls. First fn(4), which in turn calls fn(3) and fn(2) and so on.

Graphical representation of the 2 examples:

The leftmost nodes go down in descending order: fn(4), fn(3), fn(2), fn(1), which means that the height of the tree (or the number of levels) on the tree will be n.

The time complexity of this code is 2^n - 1. Although, if we count all calls will be just 9 calls for n = 4.

And the question is how we get 2^n - 1? I don't understand

Upvotes: 0

Views: 84

Answers (1)

Aleksa Majkic
Aleksa Majkic

Reputation: 803

One of the ways of calculating recursive algorithm's time complexity is using the Recursion Tree Method. For this particular case, we can write T(n)=T(n-1)+T(n-2)+2*O(1), where O(1) means constant time, since we have two comparison checks of n values using if. The recursion tree would look something like this:

1                        n
2             (n-1)               (n-2)
4        (n-2)     (n-3)     (n-3)     (n-4)
8    (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)
... 
2^i for i-th level

Total work done will be the sum of all of the work done in each level, so we can write T(n)=1 + 2 + 4 + 8 + 16 + 32 + ... = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + ... + 2^i. This is a geometric series which means that the T(n) is equal to (1-2^n)/(1-2) = (1-2^n)/(-1) = 2^n - 1. Because of that the time complexity of the function fn(n) is O(2^n).

You could also approach this using Back Substitution method. We know the following:

T(0)=1
T(1)=1
T(2)=1
T(n)=T(n-1)+T(n-2)+2*O(n)≈2*T(n-1)

Substituting T(n-2) with T(n-1) is allowed. In doing so you will get a higher bound which is still true for T(n-1)+T(n-2).

After the substitution you can also write T(n-1)=2*T(n-2), T(n-2)=2*T(n-3), ... Using these values and substituting them recursively in to the T(n) you will get:

T(n)=2*2*T(n-2)
    =2*2*2*T(n-3)
    =2*2*2*2*T(n-4)
    =...
    =2^i * T(n-i)

From there you can write n-i=1 => i=n-1 and substitute the i value in T(n). You can do this because T(1)=1 is one of the base conditions.

=> T(i)=2^(n-1) * T(n-(n-1))=2^(n-1) * T(n-n+1)=2^(n-1) * T(1)=2^(n-1)

This means that the time complexity is O(2^n).

Upvotes: 1

Related Questions