solving T(n) = 2T(n/2) + log n

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

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.