How to the examples for using the master theorem in Cormen work?
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$.