what is the complexity of this equation ?
$T(n) = 2*T(\sqrt n) + \log n$
and T(2) = 1.
what is the complexity of this equation ?
$T(n) = 2*T(\sqrt n) + \log n$
and T(2) = 1.
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.