2
$\begingroup$

$$T(n) = 2\cdot \sqrt{n} \cdot T(\sqrt{n}) + \Theta (\lg n)$$

I have been trying to solve this question but I could not find anything.

My approach:

$n = 2^k$

$S(k) = T(2^n)$ and $S(k/2) = T(2^{n/2})$

Finally: $S(k) = 2^{1+k/2} \cdot S(k/2) + c \cdot \lg(k) $

After that, I tried to build recursion tree but I can not find the sum. Do you have any ideas?

Thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ There's a very similar recurrence in this question. Do the techniques there help? $\endgroup$ – David Richerby Mar 1 '14 at 18:17
1
$\begingroup$

Let's consider the recurrence without the big $\Theta$. Then (using base two logarithms) $$ \begin{align*} T(n) &= 2n^{1-1/2} T(n^{1/2}) + \log n \\ &= 4n^{1-1/4} T(n^{1/4}) + \log n (1 + n^{1-1/2}) \\ &= 8n^{1-1/8} T(n^{1/8}) + \log n (1 + n^{1-1/2} + n^{1-1/4}) \\ &= \cdots \\ &= (\log n) n^{1-1/\log n} T(n^{1/\log n}) + \log n (1 + n^{1-1/2} + n^{1-1/4} + \dots + n^{1-1/\log n}) \\ &= 2n\log n T(2) + n\log n \left(\frac{1}{n} + \frac{1}{n^{1/2}} + \dots + \frac{1}{2}\right) \\ &= \Theta(n\log n). \end{align*} $$

$\endgroup$
  • $\begingroup$ And then prove correct by induction. $\endgroup$ – Raphael Mar 3 '14 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy