$(18$ points$)$ Derive asymptotic upper bounds for $T(n)$ in the following

recurrences. Make your bounds as tight as possible. Do not use the

master theorem. Derive your solutions from scratch. Show all

your steps in order to gain full credits $($either using the repeated expansion

method or the recursion tree method$).$ You may assume that $n$ is a power

of $4$ for $($a$),n$ is a power of $3$ for $($b$),$ and $n$ is always of a power of $5$ and

$4$ for $($c$).$

$($a$)T(1)=1$;$T(n)=8T(\frac{n}{4})+n$ for $n>1.$

$($b$)T(1)=1$;$T(n)=9T(\frac{n}{3})+n^3$ for $n>1.$

$($c$)T(1)=1$;$T(n)=T(\frac{n}{5})+T(3\frac{n}{4})+n$ for $n>1.$ Hint: Draw the

recursion tree. Examine of the sum of costs across a level. Guess a

solution. Then, try to prove by induction.