Solving Recurrence Relation With Replacement I have trouble solving this question:
T(n) = $4\sqrt{n}$ T($\sqrt{n}$) + $2n^{2}$
I write n = $2^{m}$ and than:
T($2^{m}$) = $4*2^{m/2}$ T($2^{m/2}$) + $2*2^{2m}$
and than:
S($m$) = $4*2^{m/2}$ S($m/2$) + $2*2^{2m}$
can anybody give me a hint
 A: Hint.
As
$$
\frac{T\left(n\right)}{n}=4\frac{T\left(\sqrt{n}\right)}{\sqrt{n}}+2n
$$
calling $R(n) = \frac{T\left(n\right)}{n}$ we follow with
$$
R\left(n\right)=4R\left(\sqrt{n}\right)+2n
$$
or
$$
R\left(2^{\log_2n}\right)=4R\left(2^{\log_2\sqrt{n}}\right)+2n
$$
now calling $\mathcal{R}\left(\cdot\right) = R\left(2^{(\cdot)}\right)$ and $z = \log_2 n$ we follow with
$$
\mathcal{R}\left(z\right) =4\mathcal{R}\left(\frac z2\right) + 2^z 
$$
with an analogous procedure, $\mathbb{R}\left(\cdot\right) = \mathcal{R}\left(2^{(\cdot)}\right)$ and $u = \log_2 z$ we follow with
$$
\mathbb{R}\left(u\right) = 4\mathbb{R}\left(u-1\right)+2^{2^u}
$$
with solution
$$
\mathbb{R}\left(u\right) =4^u\left(c_1+\sum_{k=0}^{u-1}2^{2^{k+1}-2k}\right)
$$
now from here we can recover $T(n)$ going backwards with $u = \log_2 z$ and $z = \log_2 n$ arriving at
$$
T(n) = \frac n4\left(\log_2 n\right)^2\left(c_1+\sum_{k=0}^{\log_2(\log_2 n)-1}2^{2^{k+1}-2k}\right)
$$
A: You can say $T(n)=\Theta(n^2)$ without replacement.
Lower bound is trivial. Use induction to show $T(n)<(4+100c)n^2$: if $\max {T(1),T(2),\cdots,T(100)}\le c$. For $n>100$, we have $$T(n)\le 4\sqrt{n}((4+100c)n)+2n^2\le 4(4+100c)/10n^2+2n^2=(3.6+10c)n^2<(4+100c)n^2$$
