Problem $2$

Give asymptotically tight upper and lower bounds for $T(n)$ in each of the following recurrences. Justify your answers.

a$.T(n)=4T(\frac{n}{3})+\sqrt[3]{n}$

b$.T(n)=4T(\frac{n}{3})+n\sqrt[3]{n}$

c$.T(n)=4T(\frac{n}{3})+(n^{lo{g}_{3}4})lo{g}_{3}n$

d$.T(n)=T(\sqrt[\phantom{2}]{n})+1$

Hint: Consider a change of variable, as discussed in the book on Page $120$ Problem $4-3$

$.T(n)=T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+n$

f$.T(n)=3T(\frac{n}{2})+nlogn$

g$.T(n)=4T(\frac{n}{2})+n^2\sqrt[\phantom{2}]{n}$

h$.T(n)=2T(\frac{n}{2})+n^3$