$19$ Standard $19-$ Solving Recurrences II: Tree Method

$19\mathrm{.}1$ Problem $1$

Problem $1.$ Consider the recurrence $T(n)$ below. Using the Tree method, determine a suitable function $f(n)$

such that $T(n)=(f(n)).$ Clearly show all steps. Note the following:

You may assume, without loss of generality, that $n$ is a power of $5($i$.$e$.,n=5^k$ for some integer $k0).$

You may hand$-$draw your tree and embed it$,$ provided it is legible and we do not have to rotate our screens

to read it$.$ However, all your calculations must be typed.

$T(n)=\{\begin{array}{ccc}(1),& if& n5\\ 2T(\frac{n}{5})+(n^2),& \text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}\text{.}& \end{array}$

Answer.