The question is :
T(n) = √2*T(n/2) + log n
I'm not sure whether the master theorem works here, and kinda stuck.
This looks more like the Akra-Bazzi theorem: http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method#The_formula with k=1
, h=0
, g(n)=log n
, a=(2)^{1/2}
, b=1/2
. In that case, p=1/2
and you need to evaluate the integral \int_1^x log(u)/u^{3/2} du
. You can use integration by parts, or a symbolic integrator. Wolfram Alpha tells me the indefinite integral is -2(log u + 2)/u^{1/2} + C
, so the definite integral is 4 - 2(log x + 2)/x^{1/2}
. Adding 1
and multiplying by x^{1/2}
, we get T(x) = \Theta(5x^{1/2} - 2 log x - 4)
.