Given the following recursive equation

$$ T(n) = 2T\left(\frac{n}{2}\right)+n\log n$$ we want to apply the Master theorem and note that

$$ n^{\log_2(2)} = n.$$

Now we check the first two cases for $\varepsilon > 0$, that is whether

  • $n\log n \in O(n^{1-\varepsilon})$ or
  • $n\log n \in \Theta(n)$.

The two cases are not satisfied. So we have to check the third case, that is whether

  • $n\log n \in \Omega(n^{1+\varepsilon})$ .

I think the third condition is not satisfied either. But why? And what would be a good explanation for why the Master theorem cannot be applied in this case?

  • 7
    $\begingroup$ See case 2 generic form in wiki. $\endgroup$
    – user742
    May 20, 2012 at 21:06
  • 4
    $\begingroup$ Case three is not satisfied because $\log n$ is not $\Omega(n^\epsilon)$ for any $\epsilon > 0$. Use l'Hôpital's rule on the limit $\frac{\log n}{n^{\epsilon}}$ $\endgroup$
    – sdcvvc
    May 20, 2012 at 21:26
  • 1
    $\begingroup$ Once you show that neither case applies, that is proof that you can not apply the master theorem as stated. $\endgroup$
    – Raphael
    May 20, 2012 at 21:53
  • $\begingroup$ Who needs the Master Theorem? Use recursion trees. $\endgroup$
    – JeffE
    Jun 17, 2012 at 11:27
  • $\begingroup$ Similar question on math.SE. $\endgroup$
    – Raphael
    Jun 18, 2012 at 18:27

2 Answers 2


The three cases of the Master Theorem that you refer to are proved in the Introduction to Algorithms by Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest and Clifford Stein (2nd Edition, 2001).

It is correctly observed that the recurrence in question falls between Case 2 and Case 3. That is $f(n) = n \log n$ grows faster than $n$ but slower than $n^{1+\varepsilon}$ for any $\varepsilon > 0$.

However the theorem can be generalized to cover this recurrence. Consider

Case 2A: Consider $f(n) = \Theta (n^{\log_b a }\log_b^k n)$ for some $k\geq 0$.

This case reduces to Case 2 when $k = 0$. It is intuitively clear that along each branch of the recurrence tree $f(x)$ is being added $\Theta (\log_b n)$ times. A sketch of a more formal proof can be found below. The final result is that

$$T(n) = \Theta (n^{\log_b a }\log_b^{k+1} n).$$

In the Introduction to algorithms this statement is left as an exercise.

Applying this statement to the recurrence in question we finally get

$$ T(n) = \Theta(n \cdot \log^2 n). $$

More details on the Master Theorem can be found in the excellent (imho) Wikipedia page.

As @sdcvvc points in the comments to prove that Case 3 does not apply here one can invoke L'Hospital's rule that says that

$$ \lim_{x\to c} \frac{f(x)}{g(x)} = \lim_{x\to c} \frac{f^\prime(x)}{g^\prime(x)} $$

for any functions $f(x)$ and $g(x)$ differentiable in the vicinity of $c$. Applying this to $f(n) = n \log n$ and $g(n) = n^{1+\varepsilon}$ one can show that $\log n \not\in \Theta (n^{1+\varepsilon}).$

Sketch of the Proof of the Master Theorem for Case 2A.

This is a reproduction of parts of the proof from Introduction to Algorithms with the necessary modifications.

First we prove the following Lemma.

Lemma A:

Consider a function

$$ g(n) = \displaystyle \sum_{j=0}^{\log_b {n-1}} a^j h(n/b^j) $$

where $h(n) = n^{\log_b a} \log_b^k n.$ Then $g(n) = n^{\log_b a} \log_b^{k +1} n.$

Proof: Substituting the $h(n)$ into the expression for $g(n)$ one can get $$g(n) = \displaystyle n^{\log_b a} \log_b^k n \; \sum_{j=0}^{\log_b{n-1}} \left(\frac{a}{b^{\log_b a}}\right)^j = n^{\log_b a} \log_b^{k +1} n.$$


If $n$ is an exact power of $b$ given a recurrence

$$ T(n) = a T(n/b) + f(n),\quad T(1) = \Theta(1) $$

one can rewrite it as

$$ T(n) = \Theta(n^{\log_b a}) + \displaystyle \sum_{j=0}^{\log_b n - 1} a^j f(n/b^j). $$

Substituting $f(n)$ with $\Theta(n^{\log_b a} \log_b^k n)$, moving $\Theta$ outside and applying Lemma A we get

$$T(n) = \Theta (n^{\log_b a }\log_b^{k+1} n).$$

Generalizing this to an arbitrary integer $n$ that is not a power of $b$ is beyond the scope of this post.


The Akra-Bazzi theorem is a strict generalization of the master theorem. As a bonus its proof is a blizzard of integrals that will make your head spin ;-)

In any case, Sedgewick in his "Introduction to the analysis of algorithms" argues convincingly that one should strive to prove $T(n) \sim g(n)$ type asymptotics.


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.