## DESIGN AND ANALYSIS OF ALGORITHM

Examples based on substitution method and Recursive calls
20 November, 2016

Ex-2.     T(n) = T(n-1) + n                                 if n>1
= 1                                              if n= 1

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

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

= T(n-3) + T(n-2)+(n-1)+n
….  …..    ….  …. (n-1) times

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

= (n(n+1))/2 = θ(n²)

Ex-3-      T(n) = n*T(n-1)              if n>1

= 1                         if n=1

Sol=        T(n)  = n* T(n-1)
= n*(n-1)*T(n-2)
= n*(n-1)*(n-2)*T(n-3)
……………..      Repeat (n-1) times

= n*(n-1)*(n-2)*………T((n)-(n-1))
= n*(n-1)*(n-2)*………(n)-(n-2)*T(1))
= o(n^n).

Ex4-   T(n) = T(n-1) + 1/n            if n>1

=1                            if n=1

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

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

= n-1 times
=  T(n-(n-1))  + 1/n-(n-2) + 1/n-(n-3)+….+ 1/n
=1/1+1/2+1/3+……1/n
=  log(n)

=O(logn)

Ex-5-          T(n)= T(n-1) + logn                        if n>1

= 1                                           n=1

Sol=                 T(n-1) + logn
[t(n-2)+log(n-1)]+ logn
T(n-3)+log(n-2)+log(n-1)+logn
……repeat (n-1 )times

T(1)+ log[n-(n-2)]+ log[n-(n-3)]+ .. . + logn
1 + log(2)+log(3) + log 4 …+ logn
1 + log(2.3.4….n)
1+log(n!)
nlogn

The recursion tree method is good for recursive execution of an algorithm. The recursion-tree method can be unreliable, generating guesses for the substitution method.
The recursion-tree method promotes intuition,just like any method that uses ellipses (…).

Next we will start Divide and Conquer Method..

Till den have fun ..