Find recurrence relation of $T(n)=2T\left(\left\lfloor\sqrt{n}\right\rfloor\right)+\log(n)$

Question

Sorry about the formatting of the title I'm not sure of the codes to make it look better.

I need to find the recurrence relation of the following:

$$T(0) = 1$$

$$T(n) = 2T\left(\left\lfloor\sqrt{n}\right\rfloor\right)+\log(n)$$

I assume this is going to be done via substitution method and through induction, but I have no idea how to set it up/solve it.

The answer is $T(n)=\theta\left(\log\,n \cdot\log\log\,n\right)$

Answer 1

Making the exponential tower one higher, let $n = 2^{2^m}$. Then $\lfloor \sqrt{n} \rfloor =\lfloor \sqrt{2^{2^m}} \rfloor =\lfloor 2^{2^{m-1}} \rfloor $ and $\log n =\log 2^{2^m} = 2^m $.

The recurrence becomes $T(2^{2^m}) =2T(2^{2^{m-1}})+2^m $.

Let $S(m) =T(2^{2^m}) $. Then $S(m) =2S(m-1)+2^ m $ or, dividing by $2^m$, $2^{-m}S(m) =2^{-(m-1)}S(m-1)+1 $. Letting $2^{-m}S(m) =U(m) $, $U(m) =U(m-1)+1 $.

Summing, $U(m) = m$ so $S(m) =m2^m $.

Finally, $T(m) =S(\log \log m) =(\log \log m)2^{\log \log m} =\log m \log \log m $.

This avoids appealing to a "well known recurrence".

Answer 2

Hint: Let $n = 2^m$. The recurrence becomes $$ T(2^m) = 2\,T(2^{m/2}) + m $$ (assuming logs to the base 2). Then let $T(2^m) = S(m)$, giving us the recurrence $$ S(m) = 2\,S(m/2)+m $$ This is a well-known recurrence with solution $S(m) = \Theta(m\log m)$, from which we can conclude (since $\log n = m$), $T(n) = \Theta(\log n\,\log\log n)$. Now just fill in the details.