How can I prove that $T(n)=\sqrt{n}T(\sqrt{n})+n$ grows as $\Theta(n\log \log{n})$?
You can use repeated substitution:
$$
\begin{align*}
T(n) &amp;= n + \sqrt{n}T(\sqrt{n}) \\ &amp;=
n + n + n^{3/4} T(n^{1/4}) \\ &amp;=
n + n + n + n^{7/8} T(n^{1/8}) \\ &amp;= \cdots
\end{align*}
$$
You reach the base case after after $\ell$ iterations when $n^{1/2^\ell} = 2$ (say), whose solution is $\ell = \log_2\log_2 n$. Assuming for simplicity that $T(2) = 0$, we get $T(n) = n\log_2 \log_2 n$.