Recursive Algorithm Analysis

Question

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

• David Richerby: There's a very similar recurrence in this question. Do the techniques there help?

Answer 1

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*} $$

• Raphael: And then prove correct by induction.