CODEWITHSUNDEEP
algorithmrecurrence
Coco Loco
Coco Loco

Reputation: 1

Find Time Complexity of Function where the recursive call is in a for loop

Here is my function:

function a(n)

     print 'a'
     if n == 0:
        return 
     for (int i = 0; i<=n-1; i++):
        a(i)
     return

So basically I understand that for each call, we're also calling all the function numbers leading to n recursively and then for each function we do the same thing again. My main problem, however, is that the for loop leaps up to a variable number every time, so it's like doing recursion inside of recursion.

Upvotes: 0

Views: 1495

Answers (3)

souparno majumder
souparno majumder

Reputation: 2052

1. T(n) = n + T(n-1) + T(n-2) + T(n-3) + .... + T(1)
// Replace n with n-1
2. T(n-1) = n - 1 + T(n-2) + T(n-3) + .... + T(1)

Replace T(n-2) + T(n-3) + .... + T(0) with T(n-1) in 1st Equation

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

     = 2 * (2 * T(n-2) + 1) + 1 // Using T(n-1) =  2 * T(n-2) + 1
     = 4*T(n-2) + 2 + 1 
     = 4*(2*T(n-3) + 1) + 2 + 1 // using T(n-2) = 2*T(n-3) + 1 
     = 8*T(n-3) + 4 + 2 + 1
     = (2^3)*T(n-3) + 2^2 + 2^1 + 2^0

if we keep replacing T(n-k) with T(n-k-1) eventually we will have

T(n) = 2^n + 2^(n-1) + .... + 2^2 + 2^1 + 2^0 //since T(1) = 1

the above function is a g.p series sum and using the formula a*(r^n -1)/(r-1)

putting a = 1, r = 2, we get.

T(n) = 2^n -1

Upvotes: 0

Ronald
Ronald

Reputation: 2872

Does it terminate in the first place?

For n == 0, it just returns. But for n == 1, it'll call itself for n == 0, n == 1 and n == 2. Thus calling a(1) will cause another call of a(1)...

IOW this is an endless loop and will show an infinite complexity.

Now after the change of the algorithm it will terminate. So let me investigate it anew.

For n == 1 it'll only call itself with n == 0.

For n == 2 it'll call itself for n == 0, n == 1 and another n == 0 due to the n == 1; that makes 3 calls.

For n == 3 it'll call itself 3 times + 3 times + 1 time, makes 7 times.

For n == 4 it'll call itself 4 times + 7 times + 3 times + 1 time, makes 15 times.

This looks very much like O(2^n - 1) = O(2^n).

(It's easy to prove by induction; The number of calls will be 2^n - 1, which is obviously true for all examples above. Given it is true for some n, it'll easily follow that it's true for n + 1)

Since the proof by induction isn't obvious for the OP, here it is:

First of all, since apart from the loop nothing really happens within the function, it'll only add a constant number of operations per iteration, which means it'll be sufficient to count the calls to itself.

By the above, it is proved for n = 1.

Now assume it has been proved for some n. We'll now follow it is true for n + 1.

By the induction hypothesis the number of calls for a(n + 1) = n + 1 + \sum_{i=0}^n (2^i - 1) (sorry for the notation; it would have worked on mathexchange. It states "the sum for i going from 0 up to n of (2^i - 1)").

Now n + 1 + \sum_{i=0}^n (2^i - 1) = \sum_{i=0}^n (2^i) = 2^{n + 1} - 1 which had to be shown.

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

Upvotes: 2

User_67128
User_67128

Reputation: 1250

Analysis by @Ronald is absolutely right.

Here is a different version of the program to get a count for how many times recursion is happening for different values of n

public class FindingRec
{

   static int count;

   static void rr(int n)
   {
      count++;
      // System.out.print(n + ", ");
      if (n == 0)
         return;

      for (int i = 0; i < n; i++)
      {
         rr(i);
      }
   }

   public static void main(String[] args)
   {
      for (int n = 0; n < 10; n++)
      {
         count = 0;
         rr(n);
         System.out.println("For n = " + n + ", Count: " + count);
      }
   }
}

And here is the output:

For n = 0, Count: 1
For n = 1, Count: 2
For n = 2, Count: 4
For n = 3, Count: 8
For n = 4, Count: 16
For n = 5, Count: 32
For n = 6, Count: 64
For n = 7, Count: 128
For n = 8, Count: 256
For n = 9, Count: 512

So, the complexity is exactly O(2^n).

Upvotes: 0

Related Questions