Question

Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for n≤2. Make your bounds as tight as possible, and justify your answer.
*Hint : You can use Master method to obtain Θ(.).

(a) T(n) = 4T(n/4) + 5n
(b) T(n) = 4T(n/5) + 5n
(c) T(n) = 5T(n/4) + 4n
(d) T(n) = 25T(n/5) + n^2
(e) T(n) = 4T(n/5) + lg n
(f) T(n) = 4T(n/5) + lg^5 n sqrt(n)
(g) T(n) = 4T(sqrt(n)) + lg^5 n
(h) T(n) = 4T(sqrt(n)) + lg^2 n
(i) T(n) = T(sqrt(n)) + 5

Answer 1

Master theorem :

T(n) = aT(n/b) + Θ(n^klog_b^p n ) where a >= 1, b >= 1, k >= 0 and p is any real number

1. If a > b^k then T(n) = Θ(n^log_ab)

2. If a = b^k and

a. p > -1 then T(n) = Θ(n^log_ab log_b^p+1 n)

b. p = -1 then T(n) = Θ(n^log_ab log_blog_b n)

c. p < -1 then T(n) =  Θ(n^log_ab)

3. If a < b^k and

a. p > 0 then T(n) =  Θ(n^k log_b^p n)

b. p <= 0 then T(n) =  Θ(n^k)