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

Question

I am trying to find temporary difficulty for repetition:

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

I am pretty close to a solution, however, I ran into an obstacle. I need to decide:

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

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

Answer 1

When you start to deploy recursion, you get:

---

Here is the same with a few extra steps:

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

Substituting k back into the equation you 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

Impossible to solve

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

for k, since if n> 1, then n ^x > 1 for any nonzero x. The only way you could solve this is to choose 1/2 ^k = 0, but that is not possible.

However, you can solve the following:

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

First, take the magazine on both sides:

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

Then multiply both sides by 2 ^k :

log n = 2 ^k

Finally, take the log again:

lg lg n = k

Therefore, this recurrence will stop as soon as k = log lg n.

Although you were only asking for the value of k, since a full year has passed since you asked, I thought I wanted to indicate that you can do a variable change to solve this problem. Try setting k = 2 ⁿ . Then k = log n, so your recurrence

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

This solves (using the main theorem) the value T (k) = & Theta; (k log k) and using the fact that k = log n, general recursion is solved in & Theta; (log n log log n).

Hope this helps!

Answer 3

dude, if it were a quick view that was equal to:

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

Try using induction to prove your affection

Answer 4

log base none of 1 equals 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 none of 0 is negative infinity .. so ...

k = -infinity.

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