# Complexity of recurrence equation

what is the complexity of this equation ?

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

and T(2) = 1.

-
add comment

## 1 Answer

By an easy induction, $f(2^{2^n}) = (n+1)2^n$, suggesting that the answer would be $(\log \log n + 1) \log n$. Plugging this into the equation, this is indeed true.

-
add comment