How to the examples for using the master theorem in Cormen work?

Problem Detail: 

I'm reading Cormen's Introduction to Algorithms 3rd edition, and in examples of Master Method recursion solving Cormen gives two examples

1. $3T( \frac{n}{4} ) + n\log(n)$
2. $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)$.

Asked By : Vahagn Babajanyan

Answered By : Reza

I think you used that method wrong! As mentioned in master theorem case 3. In your case you should use case 3 which uses $\Omega$-notation which describes asymptotic lower bound. So the solution in the book is correct!

You used $O$-notations which is and asymptotic upper bound! Be careful about which cases in master theorem you are using!

To satisfy the second case you should also have $af(n/b) \leq cf(n)$ for some $c < 1$ and large $n$. In your case, $f(n) = n \log(n)$. $a=3$, $b=4$ you should show that

$\qquad 3(n/4 \cdot \log(n/4)) \leq c n \log(n)$.

For large $n$ you could select $1 \geq c \geq 0.75$ which solves your equation.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9390