Question $4(25\mathrm{.}0$ marks$)$

Recursion

For each of the following recurrence relations, determine the runtime $T(n)$

complexity. Use the Master Theorem to solve the recurrence relations if the

recurrence relations can be solved using Master Theorem, otherwise use

expansion $($or recursive substitution$)$ to solve the recurrence relations. You must

show all your working to justify your answer. Solution without clear justification

or steps scores no mark.

$($a$)T(n)=2T(\frac{n}{2})+n^{2}lo{g}_2^{2}n,$ and $T(1)=1$

$(5\mathrm{.}0$ marks$)$

$($b$)T(n)=4T(\frac{n}{2})+\frac{n^2}{lo{g}_{2}n},$ and $T(1)=1$

$(5\mathrm{.}0$ marks$)$

$($c$)T(n)=4T(\frac{n}{4})+n^2+n,$ and $T(1)=1$

$(5\mathrm{.}0$ marks$)$

$($d$)T(n)=4T(\frac{n}{2})+8n^3,$ and $T(1)=1$

$(5\mathrm{.}0$ marks$)$

$($e$)T(n)=T(n-1)+4(n-1)+c,$ and $T(1)=1.$

$(5\mathrm{.}0$ marks$)$