Solving the recurrence T(n) = 2T(sqrt(n))

Question

I would like to solve the following recurrence relation:

T(n) = 2T(√n);

I'm guessing that T(n) = O(log log n), but I'm not sure how to prove this. How would I show that this recurrence solves to O(log log n)?

Answer 1

One idea would be to simplify the recurrence by introducing a new variable k such that 2^k = n. Then, the recurrence relation works out to

T(2^k) = 2T(2^k/2)

If you then let S(k) = T(2^k), you get the recurrence

S(k) = 2S(k / 2)

Note that this is equivalent to

S(k) = 2S(k / 2) + O(1)

Since 0 = O(1). Therefore, by the Master Theorem, we get that S(k) = Θ(k), since we have that a = 2, b = 2, and d = 0 and log_b a > d.

Since S(k) = Θ(k) and S(k) = T(2^k) = T(n), we get that T(n) = Θ(k). Since we picked 2^k = n, this means that k = log n, so T(n) = Θ(log n). This means that your initial guess of O(log log n) is incorrect and that the runtime is only logarithmic, not doubly-logarithmic. If there was only one recursive call being made, though, you would be right that the runtime would be O(log log n).

Hope this helps!