Asymptotic solution of recurrence equation I need help to find asymptotic solution of this recurrence equation
$T(n)=\sqrt{n}T(\sqrt{n})+cn$ where $c$ is constant.
 A: Here are two thoughts, either one may help.
$$\begin{split}
T(n) &= n^{1/2} T\left(n^{1/2}\right) + cn \\
     &= n^{1/2} \left[ n^{1/4} T\left(n^{1/4}\right)+cn^{1/2} \right] + cn\\
     &= n^{1/2+1/4} T\left(n^{1/4}\right) + cn^{1/2+1/2} + cn\\
     &= n^{1/2+1/4} \left[ n^{1/8} T\left(n^{1/8}\right)+cn^{1/4} \right] + 2cn\\
     &= n^{1/2+1/4+1/8} T\left(n^{1/8}\right) + 3cn \\
     &= \ldots \\
     &= n^{1-1/2^k} T\left(n^{1/2^k}\right) + kcn \\
     &= \ldots \text{ let } k = \log \log n
               \text{ so } 2^k = \log n
               \text{ and } n^{2^{-k}} = n^{1/\log n} = 2
               \ldots\\
     &= \frac{n}{2} T\left(2\right) + cn\log \log n \\
     &= \Theta (n \log \log n)
\end{split}$$
A different approach is to divide by $n$:
$$
\frac{T(n)}{n} = \frac{T \left( \sqrt{n} \right)}{\sqrt{n}}+c
$$
and changing variables to $S(n) = T(n)/n$ yields $S(n) = S\left(n^{1/2}\right)+c$, which should be easier to solve that the one above directly.
A: The change of variable
$$S(k)=2^{-2^k}T(2^{2^k})\implies S(k)=S(k-1)+c\implies S(k)=\Theta(k)$$
suggests (but cannot prove) that
$$
T(n)=\Theta(n\log\log n).
$$
