Time Analysis of Recursive Program | Back Substitution Method

Back Substitution method

 

Let’s understand the time complexity of a recursive function with some example:

 

Example:
 int test(int n)  
 {  
   if(n > 20)  
    return test(n/2) + test(n/2); //recursive call  
 }  


For solving the test(int n), let's say that time taken is T(n). In the above function, “if-condition” will take some constant time then we gonna calculate two test(n/2) and summing it up. So, there some constant terms involving for “if-condition” and for the addition operation in the recursive call.

 

T(n) = c + 2T(n/2)

This is how we should write a recursive function and then we should try solving the recursive function.


Back Substitution meethod. 

There are many ways to solve the recursive function, one of the ways are: Back Substitution method.


 //Example 1:  
 int test(int n)  
 {  
   if(n > 1)   //base condition  
    return test(n-1);  //recursive call  
 }  
 //Time Complexity = O(n)   

 

If we assume that the time taken for test(int n) is T(n) then, the time is actually some constant term for comparison and after that time taken to solve the problem on (n-1) inputs.

 

T(n) = 1 + T(n-1) ; when n>1 --------> (1)

        = 1                ; when n=1

We represent the constant term using 1 or c.

 

Back substitution can be applied to any of the problems but it is slow.

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

T(n-2) = 1+T(n-3) -------->(3)

 

Substituting eq(2) in (1);

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

T(n) = 2+T(n-2) -------->(4)

 

Substituting eq(3) in (4)

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

T(n) = 3+T(n-3)

   -

   -

   -

   -

T(n) = k+T(n-k) -------->(5)

Checking the base case of the given algorithm, we find that,

T(n) = 1+T(n-1) ;valid when n>1

n is going to start from a very large number and gonna gradually decrease and at some point, n will be 1, so whenever it reaches to 1, we’ll stop.

T(n) = k+T(n-k), This will get eliminated when there will be T(1) then.

n-k = 1

K = n-1

 

Putting the value of k in eq (5),

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

=(n-1)+T(1)

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

=n

 

Therefore, T(n) = n = O(n)


Example 2: Try it yourself.

T(n) = n+T(n-1) ; when n>1

        = 1              ; when n=1

Answer: Time complexity will be O(n^2).


Related post:

If you like this post and find it useful then you can show your support by donating a small amount from your heart. You can also show your support by following us on Facebook and Twitter.

Post a Comment

Previous Post Next Post