1
$\begingroup$

what is the complexity of this equation ?

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

and T(2) = 1.

1 Answers 1

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.