1
$\begingroup$

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..

$\endgroup$
  • 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
2
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$

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