According to Introduction to algorithms by Cormen et al, $$T(n)=2T(n/2)+n\log n$$ is not case 3 of Master Theorem. Can someone explain me why?

And which case of master theorem is it?

  • $\begingroup$ Have you tried actually applying the Master theorem? (Note that the Master theorem can not solve all recurrences.) As for why case 3 does not apply, see here: $\log n \in o(n^{\varepsilon})$ for all $\varepsilon > 0$. $\endgroup$
    – Raphael
    Apr 13 '14 at 13:10

$\log n$ grows slower than $n^\epsilon$ for any $\epsilon>0$. Thus $n\log n$ grows slower than $n^c$ for any $c>1$. However, the third case of the Master theorem requires the existance of a $c>1$ so that $n\log n$ grows at least as fast as $n^c$ (up to a constant factor).

The function is covered by the second case of the Master theorem as given in Wikipedia.

  • $\begingroup$ it is also not under second case $\endgroup$
    – tanmoy
    Apr 13 '14 at 12:24
  • 1
    $\begingroup$ @tan It falls into the general edition of the second case. $\endgroup$
    – hengxin
    Apr 13 '14 at 12:31
  • $\begingroup$ @hengxin: tell me how? $\endgroup$
    – tanmoy
    Apr 13 '14 at 12:37
  • 1
    $\begingroup$ @tan How about you click on the link and read the version given in Wikipedia? If you still don't see, why that case applies, please give a specific objection. $\endgroup$
    – FrankW
    Apr 13 '14 at 12:41
  • $\begingroup$ @FrankW: As $nlogn$ is not $\Theta(n)$, this recurrence can't be solved by second case of Master theorem(see my answer). $\endgroup$
    – tanmoy
    Apr 13 '14 at 14:06

Case 3 of Master Theorem:

If $f(n)=\Omega(n^{\log_b a+\epsilon})$ for some constant $\epsilon > 0$, and if $f (n/b) ≤ cf (n)$ for some constant $c < 1$ and all sufficiently large $n$, then $T (n) = \Theta(f (n))$.

Here $f(n)=n\log n$ and $n^{\log_ba}=n^{\log_2 2}=n^1=n$. So $n^{log_ba+\epsilon}=n^{1+\varepsilon}$. But $n\log n$ is not $\Omega(n^{1+\epsilon})$.

So it is not under case 3. It is also not under second case: If $f(n)=\Theta(n^{\log_ba})$, then second case can be applied. But here $n^{\log_ba}=n$ and $f(n)=n\log n$ is not $\Theta(n)$.

This recurrence can't be solved by Master method.

  • 1
    $\begingroup$ Please clarify this answer. I can think of at least three different ways that "n^log(b)a+$\varepsilon$" could be parsed. $\endgroup$ Apr 13 '14 at 12:38
  • $\begingroup$ @DavidRicherby: now this can be uniquely parsed. $\endgroup$
    – tanmoy
    Apr 13 '14 at 13:22

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