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

This question already has an answer here:

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?

## marked as duplicate by Raphael♦Apr 13 '14 at 13:12

• 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 – tanmoy Apr 13 '14 at 12:24
• @tan It falls into the general edition of the second case. – hengxin Apr 13 '14 at 12:31
• @hengxin: tell me how? – tanmoy 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. – FrankW 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). – 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.

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