I am trying to find the order of growth ($O(n)$, $O(n\log n)$) of the recurrence $T(n) = \sqrt{n} \cdot T\bigl(\sqrt{n}\bigr) + n$.
I started to unroll the recurrence and found that I can rewrite it in the form:
$$T(n) = n^{\frac{2^k - 1}{2^k}}\cdot T(n^{\frac{1}{2^k}}) + kn$$
My with the thought of solving the equation $n^{\frac{1}{2^k}} = 1$ in terms of $k$ and thus finding the value of the recurrence.
The problem is that $k = \infty $, which leads me to the thought that I went to the wrong direction.
How can I find the solution for this recurrence.
P.S. I know that the solution is $O(n \cdot \log \log n)$, but I do not want to start with it.
P.S.2 This is not a homework, just trying to refresh my math knowledge for analysis of recurrences in programming.
Thanks to Peter's comment, I found the solution: $T(n) = n^{\frac{2^k - 1}{2^k}}\cdot T(n^{\frac{1}{2^k}}) + kn$.
Using not 1, but 2 as the stopping point: $n^{\frac{1}{2^k}} = 2$, which means that $k = \log \log n$.
Putting it back to the equation: $T(n) = n^{\frac{\log n - 1}{\log n}}\cdot T(2) + n \log \log n$, which means that the order of growth is $O(n \log \log n)$