$$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.
Rewriting $T(n)=2⋅\sqrt{n}⋅T(\sqrt{n})+Θ(\lg n)$ in terms of
$$n=a^{2^k}\ \text{ and }\ S(k)=T(a^{2^k})⋅a^{-2^k}⋅2^{-k}$$
for some $a>1$ results in the recursion
$$S(k)⋅a^{2^k}⋅2^k=2⋅a^{2^{k-1}}⋅S(k-1)⋅a^{2^{k-1}}⋅2^{k-1}+Θ(2^k⋅\lg a)$$
or after collection
$$S(k)=S(k-1)+a^{-2^k}⋅Θ(\lg a),$$
so that
$$S(k)=S(0)+\sum_{j=1}^k a^{-2^j}⋅Θ(\lg a)$$
and this is bounded by the geometric series, and probably sharper upper bounds exist, the estimates of the Newton-Kantorivich theorem look similar.
So essentially, this $S(k)$ is a constant, and $k=\log_2(\log_a(n))$, rendering
$$T(n)=n⋅\log_a(n)⋅S(\log_2(\log_a(n)))=Θ(n⋅\log_a(n))$$
