Solve the recurrence relation:$ T(n) = \sqrt{n} T \left(\sqrt n \right) + n$ $$T(n) = \sqrt{n} T \left(\sqrt n \right) + n$$
Master method does not apply here. Recursion tree goes a long way. Iteration method would be preferable.
The answer is $Θ (n \log \log n)$.
Can anyone arrive at the solution.

Let $n=2^{2^u}$, thus we get:
$$T(2^{2^u})=2^{2^{u-1}}T(2^{2^{u-1}})+2^{2^{u}}$$ Now divide both sides by $2^{2^u}$ to get (Note that $2^{2^{u-1}}/2^{2^u}=2^{-2^{u-1}}$)
$$2^{-2^u}T(2^{2^u})=2^{-2^{u-1}}T(2^{2^{u-1}})+1$$
$$2^{-2^u}T(2^{2^u})-2^{-2^{u-1}}T(2^{2^{u-1}})=1$$
By summing from 1 to n we get:
$$2^{-2^n}T(2^{2^n})-2^{-1}T(2)=n$$
therefore:
$$T(2^{2^n})=2^{2^n}(2^{-1}T(2)+n)$$
