Time Complexity of Recursive Algorithm

In the previous post, we have seen the complexity analysis of iterative algorithms. Here, we will do the complexity analysis of recursive algorithms.

Recursion is a process in which a function call itself directly or indirectly.

 A(n)

 {

 If()

 return (A(n/2)+A(n/2))

 }

The above function has two recursive call in return statement of the program and a one conditional check if statement.

Hence, the recursive relation for this algorithm will be.

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

Here, C represent the constant time taken to check the if condition, and 2T(n/2) is the two recursive calls.

To solve the recursive relation of the given algorithm, we have three methods

1> Back Substitution

2> Tree Method

3> Masters Method.

Back Substitution method

Example:

A()

{

if(n>1)

return (A(n-1))

}

Before writing the recursive relation for the following algorithm, we will see the stopping if condition of the algorithm.

if (n>1), than the recursive call keep on continue until the value of the n  becomes 1.

Hence, the recursive relation of the above function will be.

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

T(1) = 1                n=1

To solve it, we will use back substitution method.

let

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

Use Eq(1) to calculate the iteration after (n-1)

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

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

Similarly, use Eq(1) for the iteration after (n-2)

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

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

:         :           :

:         :           :

:         :           :

T(n-K)=C+T(n-K-1)--------------(4)

Now substitute the Eq(2) value of T(n-1) in Eq(1)

T(n)=C+C+T(n-2)----------------(5)

Similarly, substitute the Eq(3) value of T(n-2) in Eq(5)

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

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

:           :           :

:           :           :

:           :           :

T(n)=KC+T(n-K-1)----------------(6)

After the K iteration, we assume the base condition will arrive. Hence, we say recursive call will end.

i.e 

n-K-1=1

n-k=2

k=n-2

Substitute the value of K in Eq(6)

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

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

Hence, the time complexity in terms of n will be

T(n)=O(n)

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

Example 2:

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

T(1)= 1                n=1

Apply the back substitution method.

let 

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

Now, calculate the value of  T(n-1) using Eq(1)

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

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

Similarly, the calculate the value for T(n-2) using Eq(1)

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

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

Further, calculate the value for T(n-k)  using Eq(1)

T(n-k)=n-k+T(n-k)--------------(4)

Substitute the value of T(n-1) and T(n-2) -------T(n-k) consecutively in Eq(1). 

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

Substitute the value of T(n-1) in above equation

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

Similarly,  substitute the value of T(n-2) in Eq(5)

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

:          :                   :

:          :                   :

:          :                   :

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

Substitute the value of the T(n-k) in Eq(7)

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

To find base condition when the recursive iteration gets stop.

n-k=1

k=n-1

substitute the value of the k in Eq(8)

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

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

See, the series is linear

Hence, we can write it as.

=n(n+1)/2 

=n^2+n/2

Time complexity will be

T(n)=O(n^2)

:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Example 3:

T(n)=3T(n-1), if n>0 --------------(1)
T(1)=1          , if n=1

Calculate the recursive call for T(n-1) using Eq(1)

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

Similarly, calculate for recursive call T(n-2) using Eq(1)

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

Now, put the value of T(n-1) in Eq(1)
T(n)=3(3T(n-2))
T(n)=9T(n-2)-----------------------------------Eq(2)
Again substitute the value of T(n-2) in Eq(2)
T(n)=9 (3T(n-3))
T(n)=27 T(n-3)
T(n)=3^3T(n-3)  After the K iteration, we get Eq(3).
:         :
:         :
:         :
T(n)=3^kT(n-k)-----------------------------(3)

To reach to the base condition, we have set n-k=1. Put the n-k=1 in above equation

T(n)=3^kT(1)                                                                                   i.e  n-k=1,
Put the value of the k in above equation                                                k=n-1

T(n)=3^n-1
T(n)=3^n 3^-1

Hence, the time complexity in terms of n will be

T(n)=O(3^n)
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Example 4:

T(n)=2T(n-1)-1 if n>0----------------------(1)
T(1)=1 if n=1

Calculate the recursive call at T(n-1), T(n-2), T(n-3).......T(n-n+1) using Eq(1)

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

Similarly, calculate the recursive call after T(n-2) using Eq(1)

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

Similarly, calculate the recursive call after T(n-3) using Eq(1)

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

Now, put the value of T(n-1), T(n-2), T(n-3) consecutively in Eq(1)

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

Substitute the value of T(n-2) in above Eq(2)

T(n)=4(2T(n-3)-1)-3
T(n)=8T(n-3)-4-3
T(n)=8T(n-3)-7
T(n)=2^3T(n-3)-(2^3-1) After the K iteration
:                  :
:                  :
:                  :
T(n)=2^kT(n-k)-(2^k-1)

To get the base condition, we have to set n-k=1.

T(n)=2^kT(1)-2^k-1)     T(1)=1, n-k=1, k=n-1

Substitute the value of the k in above equation

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

Hence, the time complexity will be

T(n) =O(1)

Try few examples

Example 5:

T(n)=T(n/2)+1    if n>0
T(1)=1                     if n=1

Example 6:

T(n)=2T(n/2)+n   if n>0
T(1)= 1                 if n=1

Tree Based Method

Solving a recursive relation using the tree method.
In this method, we divide the problem into sub-problem of equal size.

Ex:- T(n)=aT(n/b)+f(n) 

where a>1, b>1, and f(n) is a given function.

This f(n) function is the cost of spitting the problem or recombining the sub problem

Example: T(n)=2T(n/2)+C  if n>0
                T(1) = 1                if n=1
                                                                         

Add the computation of splitting at each level, that form a series.

T(n)= C+2C+4C+8C+-----------+nC)

T(n)=C(1+2+4+8+----------------+n)---------------(1)

Consider that after 2^k iteration recursive call get end

i.e,  n=2^k

Substitute in Eq(1) the value of n

T(n)=C(2^0+2^1+2^2+2^3+-------------------+2^k)

This is GP series

                                 [ So, using the formula for sum of terms in a G.P.  :

                                  a + ar + ar2 + ar3 + …… + ar n – 1   =  a( r n – 1 )

                                                                                                     (  r  –  1 )  
 So

T(n)=C(2^0(2^K+1-1)
                (2-1)
T(n)=C(2^k 2^1-1)
substitute the value of 2^k=n
T(n)=C(2n-1)
T(n)=O(n)
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Example 2:

T(n)=2T(n/2)+n   if n>0--------------------------(1)
T(1)= 1                  if n=1

Eq(1) shows that, the n times it will take to split the problem. Hence, the recursion tree will be

In Eq(1), put n/2 in place of n for the next iteration

In Eq(1), put n/4 in place of n for the next iteration

In the abov tree, we have done n times of computation to split the job at level 0. Similarly, we have done n/2 work done at the level 1 to split into n/4. Likewise, we have done constitutive work done to split the task.

Hence, the series it form

T(n)=(n+n/2+n/4+n/8+----------------------------------n/2^k)

Assume that after the 2^k iteration out recursive call gets completed.

i.e 2^k=n

T(n)=n(1+1/2+1/4+1/8+----------------------------------1)
T(n)=O(nlog(n))