# Solving recurrence relation $T(n) \leq \sqrt{n}T(\sqrt{n}) + n$

Given the condition: $$T(O(1)) = O(1)$$ and $$T(n) \leq \sqrt{n}T(\sqrt{n}) + n$$. I need to solve this recurrence relation. The hardest part for me is the number of subproblems $$\sqrt{n}$$ is not a constant, it's really difficult to apply tree method and master theorem here. Any hint? My thought is that let $$c = \sqrt{n}$$ such that $$c^2 = n$$ so we have $$T(c^2) \leq cT(c) + c^2$$ but I does not look good.

Let $$k=k(n)$$ be the smallest positive integer such that $$n^{2^{-k}}<2$$. Equivalently $$k$$ is the smallest positive integer such that $$k>\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)&\leq n^{1/2}T(n^{1/2})+n\\ &\leq n^{1/2+1/4}T(n^{1/4})+2n\\ &\leq n^{1/2+1/4+1/8}T(n^{1/8})+3n\\ &...\\ &\leq n^{1/2+1/4+...+1/2^k}T(n^{2^{-k}})+kn\\ &=n^{1-2^{-k}}O(1)+kn\\ &\leq n^{1-1/\log_2(n)}O(1)+n\log_2(\log_2(n))\\ &=\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)))$$