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

math logarithm recurrence
Waqas picture Waqas · Oct 27, 2012 · Viewed 15.4k times · Source

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

T(n) = 2T(n1/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

Salvador Dali picture Salvador Dali · Dec 15, 2015

When you start unrolling the recursion, you get: enter image description here

Here the same thing with a few additional steps:

enter image description here

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

enter image description here

Substituting k back to the equation you will get:

enter image description here

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

Related questions

How to expand and compute log(a + b)?

I would like to know the complete expansion of log(a + b). For example log(a * b) = log(a) + log(b); log(a / b) = log(a) - log(b); Similar to this, is there any expansion for log(a + b)?

Read More
Python math module

Whenever I try to use any of the built-in functions of Python's exponentiation and logarithms module, I get an error like this: NameError: name 'sqrt' is not defined I have tried using math.sqrt(4),sqrt(4) and sqrt(4.0), but none of …

Read More
NumPy: Logarithm with base n

From the numpy documentation on logarithms, I have found functions to take the logarithm with base e, 2, and 10: import numpy as np np.log(np.e**3) #3.0 np.log2(2**3) #3.0 np.log10(10**3) #3.0 However, how do I take the logarithm with base n (…

Read More