The solution of the recurrence T(n) = T(√n) + 1 is

Explanation

Putting n = 2^m gives S(m) = S(m/2) + 1, whose solution is Θ(log m) = Θ(log log n).