Recurrence relations examples

Solve the recurrence relation T(n) = T(n/2) + lg(n) where T(1) = 1 and n = 2k for a nonnegative integer k. Your answer should be a precise function of n in closed form. Note that lg represents the log function base 2.

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

T(n/2) = T(n/4) + lg(n/2)

T(n/4) = T(n/8) + lg(n/4)

T(n/8) = T(n/16) + lg(n/8)


Substituting for T(n)

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

= T(n/4) + lg(n/2)+lg(n)

= T(n/8)+ lg(n/4)+ lg(n/2)+lg(n)

= T(n/16)+lg(n/8)+ lg(n/4)+ lg(n/2)+lg(n)


----------------------------------------------------------

----------------------------------------------------------

Suppose n= 2**k

T(n) = 1 + lg (n. n/2 . n/4. . . . . n/2**k-1)

= 1+ lg(2**k  . 2**k-1 .   2**k-2 .  …… . 2)

= 1+ lg( 2 **(1+2+3+ - - - +k))

= 1 + (1+2+3+ ----+k)

= 1+ k(k+1)/2

______________________________________________________________________________

Solve the recurrence T(n) = T(n-1) + n

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

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

        Consider n= 2**k
 T(n)  =  T(n-k) + n+n-1+n-2+n-3+ -------------+n-(k-1)
         =  T(n-k) +  n(n-1) - k(k-1)/2
         = T(n-k) +  n**2 - n -lgn(lgn-1)/2
       
Therefore, asymptotic complexity is n**2