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}.($Case $3$ of Master Theorem does not apply. And show PROOF for everything$)$

b$.T(n)=4T(\frac{n}{3})+n\sqrt[3]{n}.($Show proper proof for solving recurrences$)$

c$.T(n)=4T(\frac{n}{3})+(n^{lo{g}_{3}4})lo{g}_{3}n.($Show proper proof for solving recurrences$)$

d$.T(n)=T(\sqrt[\phantom{2}]{n})+1($Show proper proof for solving recurrences$)$

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.($Show proper proof for solving recurrences$)$

f$.T(n)=3T(\frac{n}{2})+nlogn.($Show proper proof for solving recurrences$)$

g$.T(n)=4T(\frac{n}{2})+n^2\sqrt[\phantom{2}]{n}.($Show proper proof for solving recurrences$)$

h$..($Show proper proof for solving recurrences$)$

$($use the substitution method or the master theorem but show proof$)$