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
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
No comments:
Post a Comment