Expressing the upper bound to $f(n) = n * log(n)$ as a polynomial

Question

In order to do a recursive algorithm analysis, I'm applying the master theorem. As part of that, I'm looking to find a value for $\epsilon$ so that $n \log{n} = O(n^{2-\epsilon})$.

Now, intuitively, and by playing around with some graphs drawn in Desmos, I can see that many of these values for $\epsilon$ should be possible, but I find it very hard to show this conclusively, especially since for $n^x$ with values for $x$ approaching 1, it is no longer quite clear which function outgrows which.

Any help would be greatly appreciated.

Answer 1

You may be aware that

$$\log x=\lim_{\epsilon\to 0}\frac{x^\epsilon-1}\epsilon$$ and for any positive $\epsilon$,

$$x\log x=O(x^{1+\epsilon}).$$

---

Comparison to $\log x$ for exponents $\frac12,\frac14,\frac18$:

Answer 2

There are inifinite values for $\epsilon$! For all $\epsilon \in [0, 1)$ the equation is valid. Because $\lim_{n\to\infty}\frac{\log(n)}{n^\epsilon} = 0$ for all $\epsilon > 0$.