Time Analysis of Recursive Program | Back Substitution Method

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

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 tests (n/2) and summing it up. So, there are some constant terms involving “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 method. 

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 the test(int n) is T(n) then, the time is actually some constant term for comparison, and after that time is 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 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).