Can't understand why Master Theorem fits or not a given recurrence relation I'm posting here $2$ little parts of "Introduction to Algorithms" by Thomas H. Cormen (2009):


First example:





Second example:




As you can see, in the first picture we can apply the Master Theorem (MT) and we are in the third MT case.
Whereas in the second picture we can't apply the Master Theorem because The ratio $f(n) / n^{\log_b a}$ that is equal to $n \lg n$ is asymptotically less than $n^\epsilon$ for any positive constant $\epsilon$.

I can't understand why MT fits the first example, because if we try to solve the ratio (like we did in the second example) $f(n) / n^{\log_b a}$ we get $(n^{0.207}) \lg n$ that it doesn't seem to be greater than $n^\epsilon$.

------

I think that I forgot a little detail: $ε$ should be an arbitrarily small quantity.

Here is the Master Theorem definition in the textbook:



The textbook just indicates that $ε&gt;0$, so I have considered all positive numbers greater than $0$.

But


if we assume that $ε$ is a small quantity near the zero, like $ε=0.1$ or $ε=0.2$,
and we take a sufficiently large $n$, like $n=2^{60}$,

then $(n^{0.207}) \lg n$ is greater than $n^ε$.


This is an assumption I've made, help me understand if it's correct.

Thank you.
$(n^{0.207})\lg n$ must be asymptotically greater than $n^{\epsilon}$ for some $\epsilon \gt 0$ . And that is true, for example $\epsilon = 0.207$ will do the job.
I think that I forgot a little detail:
$\epsilon$ should be an arbitrarily small quantity.

Here is the Master Theorem definition in "Introduction to Algorithms" by Thomas H. Cormen(2009):



The textbook just indicates that $\epsilon\gt 0$, so I have considered all positive numbers greater than $0$.

But if we assume that $\epsilon$ is a small quantity near the zero, like $\epsilon = 0.1$ or $\epsilon = 0.2$, then $(n^{0.207}) \lg n$ is greater than $n^\epsilon$.

For example, with $n=1024$ and $\epsilon \le 0.5$ we have that $(n^{0.207}) \lg n$ is greater than $n^\epsilon$.