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

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.

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

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

$T(n)=2T(\frac{n}{2})+nl{g}^{3}n,$ and $T(1)=1$

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

$T(n)=3T(\frac{n}{2})+nlgn,$ and $T(1)=1$

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

$T(n)=4T(\frac{n}{4})+nlgn,$ and $T(1)=1$

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

$T(n)=T(n-1)+n^2,$ and $T(0)=1$

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