Question

Give asymptotically tight upper and lower bounds for T (n) in each of

the following algorithmic recurrences. Justify your answers. Hint: Use master method.

a. T (n) = 2T (n/2) + n^3.

b. T (n) = T (8n/11) + n.

c. T (n) = 16T (n/4) + n^2.

d. T (n) = 4T (n/2) + n^2 lg n.