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$)$