substituttion method

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




return (A(n-1))





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 








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



T(n)=O(n)  answer

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