Question $2.$ Exercise $2\mathrm{.}5($a$-$j$)$ from DPV$.$ For each bound, indicate whether you used the master

theorem. If so$,$ state whether the work at the base of the recursion tree dominates, the work at the

root dominates, or the work per level is balanced. If not, show your work solving the recurrence

relation.

Theorem $1($Master theorem$).$ If $T(n)=aT(\frac{n}{b})+f(n)$ for constants $a1,b>1,$ then

$T(n)=\{\begin{array}{ccc}(n^{lo{g}_{b}a})& iff(n)=O(n^c)\text{f}\text{o}\text{r}& clo{g}_{b}a\end{array}$

$2\mathrm{.}5.$ Solve the following recurrence relations and give a $$ bound for each of them.

$($a$)T(n)=2T(\frac{n}{3})+1$

$($b$)T(n)=5T(\frac{n}{4})+n$

$($c$)T(n)=7T(\frac{n}{7})+n$

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

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

$($f$)T(n)=49T(\frac{n}{25})+n^{\frac{3}{2}}logn$

$($g$)T(n)=T(n-1)+2$

$($h$)T(n)=T(n-1)+n^c,$ where $c1$ is a constant

$($i$)T(n)=T(n-1)+c^n,$ where $c>1$ is some constant

$($j$)T(n)=2T(n-1)+1$

$($k$)T(n)=T(\sqrt[\phantom{2}]{n})+1$