what is the complexity of recurrence relation?
Yes, the answer is $\lg n \cdot \lg \lg n$:

Reason this out by expanding the recurrence and looking for a pattern:

\begin{align*}
T(n) &amp;= 2T(\sqrt{n}) + \lg n \\
     &amp;= 2( 2T( \sqrt[4]{n} ) + \log(\sqrt{n}) ) + \lg n \\
     &amp;= 2\left( 2T(\sqrt[4]{n}) + \frac{1}{2} \lg n \right) + \lg n  \\
     &amp;= 4T( \sqrt[4]{n} ) + 2 \lg n \\
     &amp;= 4( 2T( \sqrt[8]{n} ) + \lg\sqrt[8]{n} ) + 2 \lg n \\
     &amp;= 8T( \sqrt[8]{n} ) + 3 \lg n \\
\end{align*}
So as we continue expanding this and taking the square root of $n$, we will eventually bottom out where $n &lt; 2$.  To figure out how many times we can take the square root of $n$, consider $n = 2^{\lg n}$, and on each recursive call, $n$ will have its square root taken.  Ending when $n &lt; 2$ gives us:
\begin{align*}
2^{\frac{\lg n}{2^k}} &amp;= 2 \\
\frac{\lg n}{2^k} &amp;= 1 \\
\lg n &amp;= 2^k \\
k &amp;= \lg \lg n 
\end{align*}

Giving a solution of $\lg n \lg \lg n$.

Alternatively, this can be solved via variable substitution and the Master Theorem.  Substituting $m = \lg n$:
\begin{align*}
T(2^m) &amp;= 2T(2^{m/2}) + m \\
S(m) &amp;= 2S(m/2) + m 
\end{align*}
At this point the Master Theorem applies, with $a=2$, $b=2$, and $f(m) = m$.  Since
$m^{\log_b a} = m^{\lg 2} = m$, resulting in $f(m) = m = \Theta(m^{\log_b a})$.  Therefore case 2 of the Master Theorem applies, and the solution is $m \lg m$.  Substituting $m = \lg n$ gives us $T(n) = \lg n \lg \lg n$.

Edit: fixed a typo (needed to write this to exceed the minimum number of characters).