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

Unfreeze

@AaronMcDaid that would be a "function T of one parameter applied to the number n". There is no special "T notation". – Gulgee

@n.m., I don't remember ever being in this thread. Why did you message me in this question? Typo by you? – Supersonic

@AaronMcDaid there was a question by you, or somebody with a username similar to yours, asking about the "T(n) notation". It is deleted now. A typo is possible (I did type the nick by hand) but unlikely, and how many similar usernames are out there to begin with? – Gulgee

@AaronMcDaid It's in the Google cache right now webcache.googleusercontent.com/search?q=cache:http://… but I don't know for how long. – Gulgee

@AaronMcDaid Wow, apparently the thread is two years old. Someone just resurrected it. If you have deleted the comment back then, you could possibly forget about it; but then how could I see it today? It's a glitch in a matrix... – Gulgee

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!

Valiancy

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

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

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,... – Hydrastine

@Hydrastine 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. – Valiancy

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

@Solitary 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. – Valiancy

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. – Solitary

Answer 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

Auk

Thank you for this clarity of answer. – Petulant