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)?

Solution 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!

Solution 2

You can solve this easily by unrolling the recursion:

Now the recurrence will finish when T(1) = a and you can find the appropriate a. When a = 0 or 1 it does not make sense but when a=2 you will get:

Substituting the k into latest part of the first equation you will get the complexity of O(log(n)).

Check other similar recursions here:

• T(n) = 2T(n^(1/2)) + log n
• T(n) = T(n^(1/2)) + Θ(lg lg n)
• T(n) = T(n^(1/2)) + 1

Comments

[Ritwik]

how come S(k) = T(2^k)? domain is not coinciding, shouldn't it be S(k') = T(2^k)?

[templatetypedef]

Can you elaborate about what you mean about the domains not counciding? I don't get what you're asking.

[Ritwik]

I meant how can you substitute S(k) for T(2^k)? If we consider them as functions of k and 2^k, domain of T is 1,2,4,8,... And S is 1,2,3,4,...

[templatetypedef]

@Ritwik You're absolutely right that, in general, you can't make substitutions like these. Most recurrences you encounter have the nice property that they're monotonically increasing. If the recurrence is monotone increasing and you can provide a bound on its value at various nice points (powers of two, powers of three, etc.), then you can asymptotically bound the entire recurrence. That's what we're doing here. It's such a common trick to do this that you typically don't actually see anyone ever write out "it's monotone" as a justification, but it's worth seeing why that's true here.

[dev]

When you substitute S(k) for T(2^k), why is it 2S(k / 2) and not 2S(√k)?

[templatetypedef]

@dev We want to choose an x such that S(x) = T(2^(k/2)). Since S(x) = T(2^x), that means we want to choose S(k / 2) = T(2^(k/2)). If we pick S(sqrt k), we'd get T(2^(sqrt k)), which doesn't match what we need.

[dev]

It would really help if you could kindly expand the answer elaborating on comment on Jul 14 about how substituting S(k)=T(2^k) is guaranteed to maintain the bounds of the original recurrence.

[Avv]

Thank you for this clarity of answer.