How to solve the recurrence T(n) = 2T(n^(1/2)) + l

问题:

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.

回答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))

回答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!

回答3:

log base anything of 1, is 0.

so

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

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

1/2^k = 0

log(1/2)((1/2)^k) = log(1/2)(0)

log base anything of 0 is negative infinity.. so...

k = -infinity.

I think you should use a different "final number" for n, than 1 just saying...

回答4:

dude if it were quick sort that was the equation:

The solution for this is O(n*log(n)) since now it is even smaller(T(n) ~ n^1/2) for some N it means your complexity is less than O(n*log(n)).

Try to use induction to prove your bound