what is the complexity of recurrence relation?

what is the complexity of below relation

$ T(n) = 2*T(\sqrt n) + \log n$

and $T(2) = 1$

Is it $\Theta (\log n * \log \log n)$ ?

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 \\
&= 2\left( 2T(\sqrt[4]{n}) + \frac{1}{2} \lg n \right) + \lg n \\
&= 4T( \sqrt[4]{n} ) + 2 \lg n \\
&= 4( 2T( \sqrt[8]{n} ) + \lg\sqrt[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).

StackExchange Computer Science Q#3362, answer score: 6