Recurrence Solution T (n) = 2T (sqrt (n))

Question

I would like to solve the following recurrence relation:

T (n) = 2T (? N);

I assume T(n) = O(log log n) , but I'm not sure how to prove it. How would I show that this recursion resolves to O(log log n) ?

Answer 1

One idea would be to simplify the repetition by introducing a new variable k such that 2 ^k = n. Then the recurrence relation is obtained

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

If you then give S (k) = T (2 ^k ), you will get a repetition

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

Please note that this is equivalent

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

Since 0 = O (1). Therefore, by the Master Theorem, we obtain that S (k) = & Theta; (k), since we have a = 2, b = 2 and d = 0 and log _b a> d.

Since S (k) = & Theta; (k) and S (k) = T (2 ^k ) = T (n), we obtain that T (n) = & Theta; (k). Since we chose 2 ^k = n, this means that k = log n, therefore T (n) = & Theta; (log n). This means that your initial assumption O (log log n) is incorrect and that the execution time is only logarithmic, not double logarithmic. If only one recursive call were made, you would be right that the runtime would be O (log log n).

Hope this helps!

Answer 2

This can be easily solved by deploying recursion:

Now the repetition ends when T(1) = a and you can find the corresponding a . When a = 0 or 1 it does not make sense, but when a=2 you get:

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

Check out other similar recursions:

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