snippetMinor
How to the examples for using the master theorem in Cormen work?
Viewed 0 times
theexamplesmasterusingforhowtheoremworkcormen
Problem
I'm reading Cormen's Introduction to Algorithms 3rd edition, and in examples of Master Method recursion solving Cormen gives two examples
For the first example we have $a=3$ and $b=4$ so $n^{\log_4
(3)}=n^{0.793}$ and Cormen says that if we choose $\epsilon = 0.207$ then $f(n) = n\log(n) = \Omega(n^{\log_4(3) + \epsilon})$
How? As I understand it if $\epsilon = 0.207$ then $\Omega(n^{\log_4(3) + \epsilon})= \Omega(n)$ so we have $n\log(n) = \Omega(n)$ but it's not true; But he proves that $n\log(n) = \Omega( n^{\log_4(3) + \epsilon} )$
And then he proves that for the second case $n\log(n)$ does not apply to masters method 3-rd case the same way as I prove above.
So could somebody explain me in detail how the third case of the master's theorem applies to $3T( \frac{n}{4} ) + n \log(n)$ but not to $2T( \frac{n}{2} ) + n\log(n)$.
- $3T( \frac{n}{4} ) + n\log(n)$
- $2T( \frac{n}{2} ) + n\log(n)$
For the first example we have $a=3$ and $b=4$ so $n^{\log_4
(3)}=n^{0.793}$ and Cormen says that if we choose $\epsilon = 0.207$ then $f(n) = n\log(n) = \Omega(n^{\log_4(3) + \epsilon})$
How? As I understand it if $\epsilon = 0.207$ then $\Omega(n^{\log_4(3) + \epsilon})= \Omega(n)$ so we have $n\log(n) = \Omega(n)$ but it's not true; But he proves that $n\log(n) = \Omega( n^{\log_4(3) + \epsilon} )$
And then he proves that for the second case $n\log(n)$ does not apply to masters method 3-rd case the same way as I prove above.
So could somebody explain me in detail how the third case of the master's theorem applies to $3T( \frac{n}{4} ) + n \log(n)$ but not to $2T( \frac{n}{2} ) + n\log(n)$.
Solution
First of all, please check what $O$ and $\Omega$ and the other Landau symbols mean; that should remove some of the confusion.
Note that $n \log n \in \omega(n)$, that is $n \log n$ grows properly faster than $n$, asymptotically. This can be seen by
$\qquad \lim_{n \to \infty} \frac{n \log n}{n} = \lim_{n \to \infty} \log n = \infty$.
By the same reasonining, though, $n \log n \in o(n^{1 + \varepsilon})$ for every $\varepsilon \in (0,\infty)$.
Therefore, $n \log n \in \Omega(n^\alpha)$ for all $\alpha \in [0,1]$, so in the example you can choose $\varepsilon$ arbitrarily so that $\varepsilon + \log_4(3) \leq 1$. The authors pick one, namely the largest (up to dropped decimal places).
As has been noted, that does not conclude the proof that case three applies; you still have to check that $a f\left( \frac{n}{b} \right) \le c f(n)$ for some $c>1$ and all $n>n_0$, $n_0$ some natural number.
As for the second example, my above explanation shows that there is no $\varepsilon > 0$ so that $n \log n \in \Omega(n^{\log_2(2) + \varepsilon})$, so case three can not apply here. Note that $o(f) \cap \Omega(f) = \emptyset$ for all $f$.
Note that $n \log n \in \omega(n)$, that is $n \log n$ grows properly faster than $n$, asymptotically. This can be seen by
$\qquad \lim_{n \to \infty} \frac{n \log n}{n} = \lim_{n \to \infty} \log n = \infty$.
By the same reasonining, though, $n \log n \in o(n^{1 + \varepsilon})$ for every $\varepsilon \in (0,\infty)$.
Therefore, $n \log n \in \Omega(n^\alpha)$ for all $\alpha \in [0,1]$, so in the example you can choose $\varepsilon$ arbitrarily so that $\varepsilon + \log_4(3) \leq 1$. The authors pick one, namely the largest (up to dropped decimal places).
As has been noted, that does not conclude the proof that case three applies; you still have to check that $a f\left( \frac{n}{b} \right) \le c f(n)$ for some $c>1$ and all $n>n_0$, $n_0$ some natural number.
As for the second example, my above explanation shows that there is no $\varepsilon > 0$ so that $n \log n \in \Omega(n^{\log_2(2) + \varepsilon})$, so case three can not apply here. Note that $o(f) \cap \Omega(f) = \emptyset$ for all $f$.
Context
StackExchange Computer Science Q#9390, answer score: 3
Revisions (0)
No revisions yet.