Recursive Algorithm Analysis
Let's consider the recurrence without the big $\Theta$. Then (using base two logarithms)
$$
\begin{align*}
T(n) &amp;= 2n^{1-1/2} T(n^{1/2}) + \log n \\ &amp;=
4n^{1-1/4} T(n^{1/4}) + \log n (1 + n^{1-1/2}) \\ &amp;=
8n^{1-1/8} T(n^{1/8}) + \log n (1 + n^{1-1/2} + n^{1-1/4}) \\ &amp;= \cdots \\ &amp;=
(\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}) \\ &amp;=
2n\log n T(2) + n\log n \left(\frac{1}{n} + \frac{1}{n^{1/2}} + \dots + \frac{1}{2}\right) \\ &amp;= \Theta(n\log n).
\end{align*}
$$