Solution

Given,

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

Let

$n=2^m$

So,

$\lg n=m$

and

$\sqrt{n}=2^{m/2}$

Let

$S(m)=T(2^m)$

Then,

$S(m)=2S\left(\dfrac{m}{2}\right)+m$

Using Master theorem,

$a=2,\ b=2$

So,

$m^{\log_b a}=m^{\log_2 2}=m$

Therefore,

$S(m)=O(m\lg m)$

Now put back $m=\lg n$.

So,

$T(n)=O(\lg n\lg(\lg n))$