6

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

Salvador Dali
  • 214,103
  • 147
  • 703
  • 753
Tasneem Fathima
  • 159
  • 3
  • 7
  • 15
  • @AaronMcDaid that would be a "function T of one parameter applied to the number n". There is no special "T notation". – n. m. could be an AI Dec 16 '15 at 10:32
  • 2
    @n.m., I don't remember ever being in this thread. Why did you message me in this question? Typo by you? – Aaron McDaid Dec 16 '15 at 15:02
  • @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? – n. m. could be an AI Dec 16 '15 at 18:38
  • @AaronMcDaid It's in the Google cache right now http://webcache.googleusercontent.com/search?q=cache:http://stackoverflow.com/a/19780235 but I don't know for how long. – n. m. could be an AI Dec 16 '15 at 18:48
  • 2
    @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... – n. m. could be an AI Dec 16 '15 at 18:53

2 Answers2

11

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

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

If you then let S(k) = T(2k), 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 logb a > d.

Since S(k) = Θ(k) and S(k) = T(2k) = T(n), we get that T(n) = Θ(k). Since we picked 2k = 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!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • how come S(k) = T(2^k)? domain is not coinciding, shouldn't it be S(k') = T(2^k)? – Ritwik Jul 13 '16 at 05:17
  • Can you elaborate about what you mean about the domains not counciding? I don't get what you're asking. – templatetypedef Jul 13 '16 at 13:58
  • 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,... – Ritwik Jul 14 '16 at 16:01
  • 3
    @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. – templatetypedef Jul 14 '16 at 17:16
  • When you substitute S(k) for T(2^k), why is it 2S(k / 2) and not 2S(√k)? – dev Oct 25 '16 at 17:23
  • 1
    @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. – templatetypedef Oct 26 '16 at 02:22
  • 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. – dev Oct 29 '16 at 23:48
5

You can solve this easily by unrolling the recursion:

enter image description here

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:

enter image description here

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

Check other similar recursions here:

Community
  • 1
  • 1
Salvador Dali
  • 214,103
  • 147
  • 703
  • 753