CODEWITHSUNDEEP
algorithmrecursiondata-structurestime-complexity
chandresh.v
chandresh.v

Reputation: 87

How to find the time complexity of the following recursive code?

How to derive the runtime complexity of the following program?

public void function(int n){
   if(n==1) return;
   for(int i=0;i<n;i++){
     function(i)
   }
}

function(4);

What i understand is,

T(n) = n(T(n-1));
T(n-1) = (n-1)(T(n-2))
T(n-2) = (n-2)(T(n-2))

After replacing n(T(n-1)) with subsequent expansion,

T(n) = n((n-1)((n-2)(T(n-2))))

Which is essentially nothing but 

n*(n-1)*(n-2)...1 = n!

However, in different posts, i see that this is 2^n not n!. Can anyone please explain me if I have missed anything?

Upvotes: 0

Views: 658

Answers (1)

meowgoesthedog
meowgoesthedog

Reputation: 15035

T(n) = n T(n-1) would indeed be O(N!) - but it is the wrong recurrence relation for function.

The loop runs from i = 0 to i = n-1, which means that the recursive calls are function(0), function(1), function(2) ... , function(n-1). Hence the recurrence relation is:

T(n) = T(0) + T(1) + T(2) + ... + T(n-1)

There's a neat trick to help you solve this. Consider the terms in T(n-1) and write the expansion alongside that of T(n):

T(n)   = T(0) + T(1) + T(2) + ... + T(n-3) + T(n-2) + T(n-1)
                                                      ------
T(n-1) = T(0) + T(1) + T(2) + ... + T(n-3) + T(n-2)

See where this is going? Subtract one from the other and only the underlined term T(n-1) is left:

T(n) - T(n-1) = T(n-1)
T(n) = 2 T(n-1)

This alternative form of the recurrence is now solvable in the same manner as before:

T(n) = 2^2 T(n-2)
     = 2^3 T(n-3)
     = 2^4 T(n-4)
     = ...
     = O(2^n)

q.e.d.

Upvotes: 2

Related Questions