How to the examples for using the master theorem in Cormen work? I'm reading Cormen's Introduction to Algorithms 3rd edition, and in examples of Master Method recursion solving Cormen gives two examples


$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)$.
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&gt;1$ and all $n&gt;n_0$, $n_0$ some natural number.

As for the second example, my above explanation shows that there is no $\varepsilon &gt; 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$.