substituttion method

What is the time complexity of recursive program given below using the substitution method?

 A(n)

{

if(n>1)

return (A(n-1))

}

 

 

Answer

Solution :

Recurrence Relation  is  T(n)=\left \{ 1+T(n-1) if n>1 otherwise 1 if n\leq 1\right \}

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

  T(n-1)=1+T(n-2).....(replace  n by n-1 in eq1 to get eq2)....eq2

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

substitute  the value of T(n-1) in eq1, we get

T(n)=2+T(n-2).... now again substitute  the value of T(n-2) , we  get

 T(n)=3+T(n-3)..... similarly for all 

.

.

.

.

.

.

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

now at some point, it will stop so we use stopping condition

n-k=1 .. so, k=n-1....put  the value of k in last eq and solve

=n-1+T(1)

=n-1+1

T(n)=O(n)  answer

The time complexity of this recursive  program is O(n)

 

0Comment