solving T(n) = 2T(n/2) + log n [closed]

Question

I am trying to solve T(n) = 2T(n/2) + log n

substituted n = 2^k

T(2^k) = 2T(2^(k-1)) + k  
T(2^k) = 2^2 T(2^(k-1)) + 2(k-1) + k

after k steps
T(2^k) = 2^k T(1) + 2^(k-1) + 2 * (2^(k-2)) +....+k

So basically I need to sum a term of i*2^i where i = 1 to log n - 1.
And I could not find an easy way to sum these terms. Am I doing something wrong ? Is there any other way to solve this recursion ? would master theorem work her ? if yes than how ?

Thanks.

Answer 1

first you should define a recursive export,say T(1) then: since T(2^k) = 2T(2^(k-1)) + k; * we define g(k) = T(2^k)/2^k; then * come into: g(k) = g(k-1) + k/2^k = g(1) + sum(i/2^i); i=2,3,4...k where g(1) = T(1)/2 = c;

where you could then unfold the sum expression and define it = y; then unfold the expression of y/2; y-y/2 is a geometric progression, so youcan solve it

as I worked out, sum = 3/2 - (k+2)/2^k;

so T(n) = 2^k * g(k) = (3/2+c)*n - (2+logn)

Answer 2

Wolfram|Alpha gives a closed form solution:

for a constant c_1 that is fixed by the initial condition.

By the way, log(n)/log(2) = lg(n), where lg is the base two logarithm.