Answered>Order 3160

Alogrithm

a) Using the tree method, compute an estimate of the following recurrence

 T(n) = 2T(n/2) + 3T(n/4) + cn2

b) Using substitution, prove the estimate obtained in part a

For each of the following recurrences state whether the Master theorem can be applied to solve the recurrence or not. If the Master theorem can be used, then use it to determine running time for the recurrence. If the Master theorem cannot be applied, then specify the reason (you don’t need to solve the recurrence).

a)    T(n) = 4T(n/3) + n2

b)   T(n) = 3T(n/2) + 2n

c)    T(n) = 2T(n/3) + 1

d)   T(n) = 2T(n/4) + 15n

e)    T(n) = 2/7 T(n/2) + n

f)    T(n) = T(n/2) + 2T(n/5) + n

g)    T(n) = T(n/2) + lg4 n

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