[Solved]: 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) &= 2T(sqrt{n}) + lg n \ &= 2( 2T( sqrt[4]{n} ) + log(sqrt{n}) ) + lg n \ &= 2left( 2T(sqrt[4]{n}) + frac{1}{2} lg n right) + lg n \ &= 4T( sqrt[4]{n} ) + 2 lg n \ &= 4( 2T( sqrt[8]{n} ) + lgsqrt[8]{n} ) + 2 lg n \ &= 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 < 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 < 2$ gives us: begin{align*} 2^{frac{lg n}{2^k}} &= 2 \ frac{lg n}{2^k} &= 1 \ lg n &= 2^k \ k &= 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) &= 2T(2^{m/2}) + m \ S(m) &= 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).