For each recurrence relation shown below, explain $($in a sentence or two$)$ which case of the Master Theorem applies, then use the Master Theorem to find a

$($ g$($n$)$

$)$ such that

$($ T$($n$)$

in

Theta$($g$($n$))$

$)$

Use the Master theorem to find $$ bounds for each of the recurrence relations

below. Show functions $f(n)$ and $n^{lo{g}_{b}a}.$ If the Master method does not apply,

say so and explain why. If the Master method applies, explain which case applies

and why. If you are applying Case $1$ or Case $3,$ you need to show that one of the

functions grows polynomially faster than the other and give the value of $lon$ for

which it is true $($and explain how you got it$).$ If you are applying Case $3$ of the

Master theorem, make sure to also check the regularity condition and give $C.$

You need to justify your answers to get full credit for this question.

$(1\mathrm{.}5pt)$

$T(0)=T(1)=C_1$

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

$(2pt)$

$T(0)=T(1)=C_1$

$T(n)=16T(\frac{n}{2})+n^3**lo{g}_{2}n$

$(2pt)$

$T(0)=T(1)=C_1$

$T(n)=2T(\frac{n}{4})+n^{\frac{3}{2}}$

$(2pt)$

$T(0)=T(1)=C_1$

$T(n)=9T(\frac{n}{3})+n^{2}lgn$

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

$T(0)=T(1)=C_1$

$T(n)=8T(\frac{n}{2})-n^2$