# How can I prove that $T(n)=\sqrt{n}T(\sqrt{n})+n$ grows as $\Theta(n\log \log{n})$? [duplicate]

How can I prove that if $T(n) = \sqrt{n}T(\sqrt{n}) + n$ then $T(n) = \Theta(n\log\log n)$?

I tried to define $T(n)$ by $G(n)$, prove about $G(n)$, and then to return to $T(n)$, but it's not working..

## marked as duplicate by Evil, Discrete lizard♦, David Richerby complexity-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Apr 23 '18 at 14:28

• Start by dividing both sides of the recurrence by $n$ to get $\frac{T(n)}{n}=\frac{T(\sqrt{n})}{\sqrt{n}}+1$. Write $\frac{T(n)}{n}=F(n)$. Now you have a much easier recurrence to work with: $F(n)=F(\sqrt{n})+1$ – mursalin Apr 2 '18 at 13:09
You can use repeated substitution: \begin{align*} T(n) &= n + \sqrt{n}T(\sqrt{n}) \\ &= n + n + n^{3/4} T(n^{1/4}) \\ &= n + n + n + n^{7/8} T(n^{1/8}) \\ &= \cdots \end{align*} You reach the base case after after $\ell$ iterations when $n^{1/2^\ell} = 2$ (say), whose solution is $\ell = \log_2\log_2 n$. Assuming for simplicity that $T(2) = 0$, we get $T(n) = n\log_2 \log_2 n$.