# Need help about solving a recurrence relation

I have a recurrence relation which is like the following:

$T(n) = 2T(\frac{n}{2}) + \log_{2}n$

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

$T(n)=(2\log_{2}n)(n-1)-(1\times 2 + 2\times 2^{2} + \ldots + k\times2^{k})$ where $k=\log_{2}n$

I am trying to find a theta notation for this equation. But i cannot find a closed formula for the sum $(1\times 2 + 2\times 2^{2} + \ldots + k\times2^{k})$. How can I find a big theta notation for $T(n)$?

This looks like the running time of a divide-and-conquer algorithm. You can apply the Akra-Bazzi method here. The method works for recurrences of the form:

$$T(n)=\sum_i^k a_iT(b_i n+h_i(n))+g(n), \forall n\ge n_0$$

$k=1$

$g(n)=\log n$

$a=2,b=1/2$

$h(n)=0$

For this to work, we have to find a number $p$ satisfying $ab^p=1$. That's easy,let $p=1$.

The method tells us that $T(n)=\Theta(n^p(1+\int_1^n\frac{g(x)}{x^{p+1}}dx))$

I computed the integral on WolframAlpha. The answer is $1-\frac{\log n + 1}{n}$.

Therefore, $$T(n)=\Theta(2n-\log n)=\Theta(n)$$

Here is another way of solving this. Let $n=2^m$

$T(2^m)=2(2T(2^{m-1})+(m-1))+m=2^2T(2^{m-2})+m+(m-1)=\dots=2^kT(2^{m-k})+m+(m-1)+\dots+m-k+1=2^m\Theta(1)+m(m-1)/2=\Theta(2^m)$.

So $T(n)=\Theta(n)$

• Master Theorem applies here and is easier than Akra-Bazzi. Plus if you're willing to use Wolfram Alpha you can get the recurrence solution directly. – SamM Mar 7 '13 at 20:15
• The first half makes it harder than it has to be, but +1 for the second half. – Joe Mar 8 '13 at 3:45
• @SamM The point is to expose the Akra-Bazzi method. – saadtaame Mar 8 '13 at 11:37
• @Joe Thanks! Change the order if that makes more sense to you :D – saadtaame Mar 8 '13 at 12:23

For $\sum_{0 \le r \le k} r \cdot 2^r$, start with: $$\frac{1 - z^{k + 1}}{1 - z} = \sum_{0 \le r \le k} z^r$$ As this is a polynomial, the following mangling doesn't need any justification: $$z \frac{d}{dz} \frac{1 - z^{k + 1}}{1 - z} = \sum_{0 \le r \le k} r z^r$$ Doing the operations indicated: $$\sum_{0 \le r \le k} r z^r = \frac{z^k (k z^2 - (k + 1) z) + z}{(1 - z)^2}$$ Finally: $$\sum_{0 \le r \le k} r 2^r = (2 k - 2) 2^k + 2 = \Theta(k 2^k) = \Theta(n \log n)$$

• This answer is incorrect; it is $\Theta(n)$. – SamM Mar 7 '13 at 20:17
• @SamM, Impossible, just the last term is $\Theta(k 2^k) = \Theta(n \log n)$. – vonbrand Mar 7 '13 at 20:26
• Ah, I take it back. You were solving for the term he was subtracting from the original equation, not the recurrence itself. If you substitute back in you get $T(n) = \Theta(n)$. – SamM Mar 7 '13 at 20:31