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$
$\endgroup$
1
-
$\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$– RaphaelCommented Apr 13, 2014 at 13:10
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
$\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$ Commented Apr 13, 2014 at 12:24
-
1$\begingroup$ @tan It falls into the general edition of the second case. $\endgroup$– hengxinCommented Apr 13, 2014 at 12:31
-
-
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$– FrankWCommented Apr 13, 2014 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$ Commented Apr 13, 2014 at 14:06
$\begingroup$
$\endgroup$
2
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.
answered Apr 13, 2014 at 12:25
-
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$ Commented Apr 13, 2014 at 12:38
-
$\begingroup$ @DavidRicherby: now this can be uniquely parsed. $\endgroup$ Commented Apr 13, 2014 at 13:22