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)$?


2 Answers 2


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$$

In your case:


$g(n)=\log n$



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$


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

  • 1
    $\begingroup$ 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. $\endgroup$
    – SamM
    Commented Mar 7, 2013 at 20:15
  • 1
    $\begingroup$ The first half makes it harder than it has to be, but +1 for the second half. $\endgroup$
    – Joe
    Commented Mar 8, 2013 at 3:45
  • $\begingroup$ @SamM The point is to expose the Akra-Bazzi method. $\endgroup$
    – mrk
    Commented Mar 8, 2013 at 11:37
  • $\begingroup$ @Joe Thanks! Change the order if that makes more sense to you :D $\endgroup$
    – mrk
    Commented Mar 8, 2013 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) $$

  • $\begingroup$ This answer is incorrect; it is $\Theta(n)$. $\endgroup$
    – SamM
    Commented Mar 7, 2013 at 20:17
  • 2
    $\begingroup$ @SamM, Impossible, just the last term is $\Theta(k 2^k) = \Theta(n \log n)$. $\endgroup$
    – vonbrand
    Commented Mar 7, 2013 at 20:26
  • $\begingroup$ 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)$. $\endgroup$
    – SamM
    Commented Mar 7, 2013 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.