I want to show that the requrrence $T (n) = \sqrt{n} T(\sqrt{n}) + O (n)$ is in $O(n \log \log n)$
Here's my attempt:
If we expand the recursion tree, at a level $i$, there are $n^{1/2^k}$ subproblems each requiring work equal to $n^{1/2^k}$. There are $\log \log n$ levels in this tree.
So the summation is: $\sum_{i = 0}^{\log \log n} n^{1/2^{(k-1)}}$
Is this summation correct, and how can I show it is in $O(n \log \log n)$?
For every $a\gt1$, the sequence $(S_a(k))$ defined by $$S_a(k)=a^{-2^k}\cdot T(a^{2^k}), $$ is such that $S_a(k)=S(k-1)+O(1)$, hence $S_a(k)=O(k)$, that is, $$ T(a^{2^k})=O(k\cdot a^{2^k}).$$ This means that $T(n)=O(n\log\log n)$ when $n$ is restricted to some sequence $(a^{2^k})$ but DOES NOT imply that $T(n)=O(n\log\log n)$ for the complete sequence $(T(n))$.