# $T(n)=2T(n/2)+n\log n$ and the Master theorem [duplicate]

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?

• 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$.
– 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.

• it is also not under second case Apr 13 '14 at 12:24
• @tan It falls into the general edition of the second case. Apr 13 '14 at 12:31
• @hengxin: tell me how? Apr 13 '14 at 12:37
• @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. Apr 13 '14 at 12:41
• @FrankW: As $nlogn$ is not $\Theta(n)$, this recurrence can't be solved by second case of Master theorem(see my answer). 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.

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