Recurrence - Master Theorem - Asymptotic Question Sorry if this question has been asked before, but I am trying to figure this out. I am using the CLRS text, Introduction to Algorithms. In the Recurrences chapter, in the Master Theorem section, the following example is given with the solution:

$$T(n) = 3T\left(\frac{n}4\right) + n\log n $$

Here,

$$ a = 3, b =4, f(n) = n\log n $$

Using the Master method, it says

$$f(n) = \Omega(n^{\log_4 3 + \epsilon})  $$

I don't understand how $f(n)$ was "assumed" to have this
lower bound ($\Omega$). I would be extremely greatful to anyone who points out to me why this is so.

If more details are needed to understand the problem, please let me know. I will add more details to this question.

TIA,

Jake Clawson

EDIT: I thank all those who have responded below. I have replied to each below individually. But my question still stands. The book directly goes on to say that $f(n)$ is $\Omega$. I don't understand this and this is the key to applying the Master Theorem because once $f(n)$ is known that we know which case to apply.
So you want to understand why $n\log n=\Omega(n^{\log_4 3+\epsilon})$

The easiest way is to look at the limit

$\lim_{n-&gt;\infty}\frac{n\log n}{n^c}$

which is evaluated to

$\lim_{n-&gt;\infty}\frac{\log n+1}{cn^{c-1}}$ where $c=log_4 3+\epsilon$

since $\log_4 3\lt1$, there exists $\epsilon\gt0$ such that $\log_4 3+\epsilon=c\lt1$. Therefore, the limit would tends to $\infty$ and hence $nlogn=\Omega(n^{\log_43+\epsilon})$
Take $c=\lg\left(n_{0}\right)$ in the following definition for the
$\Omega$-notation:

$$
\Omega\left(g\left(n\right)\right)=\left\{ f\left(n\right):\exists\left(c&gt;0\wedge n_{0}&gt;0\right)\backepsilon0\leq cg\left(n\right)\leq f\left(n\right)\forall n\geq n_{0}\right\} 
$$

which appears on page 48 of the third edition of the book. Thus, with
$g\left(n\right)=n$, for $n\geq n_{0}$ we have that

$$
n\lg\left(n_{0}\right)\leq n\lg\left(n\right)
$$

This shows that $f\left(n\right)=\Omega\left(n\right)$, which answers
the question.