Solving recurrence relation $T(n) \leq \sqrt{n}T(\sqrt{n}) + n$
Let $k=k(n)$ be the smallest positive integer such that $n^{2^{-k}}&lt;2$. Equivalently $k$ is the smallest positive integer such that $k&gt;\log_2(\log_2(n))$. So, $$k=\lceil \log_2(\log_2(n))\rceil$$
Using repeatedly the inequality with $n,n^{2^{-1}},n^{2^{-2}},...,n^{2^{-k}}$ we get
$$
\begin{align}
T(n)&amp;\leq n^{1/2}T(n^{1/2})+n\\
&amp;\leq n^{1/2+1/4}T(n^{1/4})+2n\\
&amp;\leq n^{1/2+1/4+1/8}T(n^{1/8})+3n\\
&amp;...\\
&amp;\leq n^{1/2+1/4+...+1/2^k}T(n^{2^{-k}})+kn\\
&amp;=n^{1-2^{-k}}O(1)+kn\\
&amp;\leq n^{1-1/\log_2(n)}O(1)+n\log_2(\log_2(n))\\
&amp;=\frac{n}{2}O(1)+n\log_2(\log_2(n))
\end{align}
$$
So, we get that $$T(n)\in O(n\log_2(\log_2(n)))$$