How can I solve this basic recurrence $T(n) = \sqrt{n} \cdot T(\sqrt{n}) + n^2$?

Question

Could someone post the detailed steps for calculating a tight upper bound of the following recurrence?

$$T(n) = \sqrt{n} \cdot T(\sqrt{n}) + n^2$$

Answer 1

Shaving the squared root seems to work out, namely set

$$S(n) := \frac{T(n)}{\sqrt{n}} = T(\sqrt{n}) + \frac{n^2}{\sqrt{n}} = T(n^{1 / 2}) + n^{3 / 2} = T(2^{k / 2}) + 2^{3k/2} \text{ via the substitution $k := \log_2 n$}$$

and solve the shorted recurrence $R(k) = R(k / 2) + 3k / 2$ via the method of the recursion tree to get a recursion tree with node weight equals $3k / 2$ and tree height $\log_2 k$, i.e. $R(k) \in \mathcal{O}(\frac{3k}{2} \log_2 k)$, since the overall weight at every level is $3k / 2$. Thus, $S(n) = 3 / 2 \cdot \log_2 n \cdot \log_2 \log_2 n$ and finally

$$T(n) = \sqrt{n} \cdot \Big (\frac{3 \log_2 n}{2} \cdot \log_2 \log_2 n\Big)$$

and it's gone. I hope that someone proofread it.

Answer 2

As

$$ T\left(2^{\log_2 n}\right)=\sqrt{n}T\left(2^{\log_2 \sqrt{n}}\right)+n^2 $$

or

$$ T\left(2^{\log_2 n}\right)=\sqrt{n}T\left(2^{\frac 12\log_2 n}\right)+n^2 $$

calling now $\mathcal{T}(\cdot) = T\left(2^{(\cdot)}\right)$ and $z = \log_2 n$ we follow with

$$ \mathcal{T}(z)=2^{\frac z2}\mathcal{T}\left(\frac z2\right)+2^{2z} $$

now calling $\mathbb{T}(\cdot) = \mathcal{T}(2^{(\cdot)})$ and $u = \log_2 z$ we follow with

$$ \mathbb{T}(u)=2^{\frac{2^u}{2}}\mathbb{T}(u-1)+2^{2\times 2^u} $$

with solution

$$ \mathbb{T}(u) = C_02^{2^u}+2^{2^u}\sum_{k=0}^u 2^{2^{k-1}} $$

now going backwards we get

$$ T(n) = C_0 n + n\left(\sum_{k=0}^{\log_2(\log_2 n)}2^{2^{k-1}}\right) $$

hence $T(n) \approx \mathcal{O}\left(n^2\right)$