This question already has an answer here:

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 Apr 23 '18 at 14:28

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ 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$ $\endgroup$ – 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$.


Not the answer you're looking for? Browse other questions tagged or ask your own question.