How to solve the recurrence T(n) = 2T(n^(1/2)) + log n? [closed]

Question

I am trying to find the time complexity for the recurrence:

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

I am pretty close to the solution, however, I have run into a roadblock. I need to solve:

n^(1/2k) = 1

for k to simplify my substitution pattern. I am not looking for answers to the recurrence, just a solution for k.

Answer 1

When you start unrolling the recursion, you get:

---

Here the same thing with a few additional steps:

Now using the boundary condition for a recursion (number 2 selected as 0 and 1 do not make sense), you will get:

Substituting k back to the equation you will get:

Here are a couple of recursions that use the same idea.

• T(n) = T(n^1/2) + 1
• T(n) = T(n^1/2) + O(loglog(n))

Answer 2

It's impossible to solve

n^(1/2k) = 1

for k, since if n > 1 then n^x > 1 for any nonzero x. The only way that you could solve this is if you picked k such that 1 / 2^k = 0, but that's impossible.

However, you can solve this:

n^(1/2k) = 2

First, take the log of both sides:

(1 / 2^k) lg n = lg 2 = 1

Next, multiply both sides by 2^k:

lg n = 2^k

Finally, take the log one more time:

lg lg n = k

Therefore, this recurrence will stop once k = lg lg n.

Although you only asked for the value of k, since it's been a full year since you asked, I thought I'd point out that you can do a variable substitution to solve this problem. Try setting k = 2ⁿ. Then k = lg n, so your recurrence is

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

This solves (using the Master Theorem) to T(k) = Θ(k log k), and using the fact that k = lg n, the overall recurrence solves to Θ(log n log log n).

Hope this helps!