Can not find the Time Complexity of Recursive Function with a single Loop

Question

Following is a Simple Recursive Function .I have made its Recurrence equation like this

T(n)=kT(n-1)+1

I have used + 1 for int i; I have Solved it like this

T(n)=kT(n-1)+1 . . . T(n)=k^mT(n-m)+m

To make T(1)-> n-m=1 -> m=n-1

it becomes ( k^n-1 )(n-1)

Now my question is ,Is it fine .I was expecting it n^2 but this is something not seems to be polynomial.

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

Kindly help me how to solve this Short problem

Well, as it's written, it doesn't *do* anything. It's just an empty loop. — Geobits, Aug 05 '13 at 00:24

Jason L · Answer 1 · 2013-08-05T03:29:33.243

Let n=size. Then

T(n,k)=k*T(n,k-1) + O(1)
    =k*[(k-1)*T(n,k-2) + O(1)] + O(1)
    =k*(k-1)*T(n,k-2) + k*O(1) + O(1)
    =k*(k-1)*[(k-2)*T(n,k-3) + O(1)] + k*O(1) + O(1)
    =k*(k-1)*(k-2)*T(n,k-3) + k*(k-1)*O(1) + k*O(1) + O(1)
    =...
    =O(k!)*T(n,0) + O(1) * [P(k,k-1)+P(k,k-2)+...+P(k,1)]
    =O(k!)*T(n,0) + O(1) * e * O(k!)
    =O(k!)*T(n,0)

So it depends on the complexity of permute(0,size).

Can not find the Time Complexity of Recursive Function with a single Loop

1 Answers1