Recurrence relation: T(n) = 2T(n/2) + log(n)

Question

I have a recurrence relation which is like the following:

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

I am using recursion tree method to solve this. And at the end, i came up with the following equation:

T(n)=(2log₂n)(n-1)-(1*2 + 2*2² + ... + k*2^k) where k=log₂n.

I am trying to find a theta notation for this equation. But i cannot find a closed formula for the sum (1*2 + 2*2² + ... + k*2^k). How can i find a big theta notation for T(n)?

Answer 1

These recurrence can be solved with a masters theorem. In your case a = 2, b = 2 and therefore c = logb(a) = 1.

Your f(n) = log n and because n^c grows faster than your f, it dominates the solution and you fall in the first case. So the complexity is O(n).