Question

Solve the following recurrence relations:

1.
T(n) = T(n/3) + n for n > 1
T(1) = 1

2.
T(n) = 4T(n/2) + n^2 for n > 1
T(1) = 1

Answer 1

T(n)

= T(n/3) + n

= T(n/9) + n/3 + n

=T(n/27)+ n/9 + n/3 + n

= T(n/3ⁱ) +n/3^i-1 + n/3^i-2 + ....... + n = n

T(n) = T(1) + n (1 + 1/3 + 1/3² + ..... + 1/3^i-1 )

= T(1) + n(1(1- (1/3ⁱ)/(1- 1/3)

= 1 + 2n/3 (1- (1/3ⁱ))

Now n/3ⁱ = 1  

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

therefore T(n) = (3n-1)/2

(b)

T(n)

= 4T(n/2) + n²

= 4 * (4T(n/4) + (n/2)² ) + n²

= 16T(n/4) + 2n²

= 4ⁱ T(n/2ⁱ)+in²

where

n/2ⁱ = 1

n = 2ⁱ

log ₂n = i

T(n) = 4^{log ₂ n} * T(1) + (log ₂n)n² = 2^{2log ₂ n} * 1 + (log ₂n)n² = n² (1 + log₂n) = n² (log₂2 + log₂n) = n²log₂(2n)

T(n) =  n²log₂(2n)