For each of the following recurrence relations, determine the runtime $()$ 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.

$1.()=4($

$$

$2$

$)+$

$2+,(1)=1(4\mathrm{.}0$ marks$)$

$2.()=2($

$$

$2$

$)+3,(1)=1(4\mathrm{.}0$ marks$)$

$3.()=3($

$$

$2$

$)+,(1)=1(4\mathrm{.}0$ marks$)$

$4.()=4($

$$

$4$

$)+,(1)=1(4\mathrm{.}0$ marks$)$

$5.()=(1)+$

$2$

$,(1)=1(4\mathrm{.}0$ marks$)$