Solving Recurrence Relation With Replacement

Question

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

Answer 1

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) $$

Answer 2

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$$