How close is $n $ to $ n \log n$?

Question

How close is $n $ to $ n \log n$?

I know $\mathcal{O}(n) < \mathcal{O}(n \log n)$

But for some small $\epsilon > 0 , n^{1+\epsilon}=n \log n$. How much small is that $\epsilon$? The reason why i got this doubt is when i was thinking to last case of master theorem $T(n)=aT(n/b) + f(n)$ namely - f(n) is logarithmically larger or asymptotically equal to $n^{\log_b a}$

Answer 1

Well, $\log n = n^{\log_n \log n} = n^{\frac{\log \log n}{\log n}}$, so $\epsilon = \frac{\log \log n}{\log n}$.

I think the important takeaway from this is that $\epsilon$ is smaller than any constant as $n \to \infty$, since $\log\log n \ll \log n$.

Answer 2

For any $\epsilon > 0$, $n^{1+\epsilon}$ grows faster than $n \log n$ (in the sense that $\frac{n^{1+\epsilon}}{n \log n} \to \infty$).

Answer 3

This is an important, iconic example, turning up in many places.

To my mind, since one-way-or-another we know that $f(x) = {\log x\over x^\varepsilon}\to 0$ as $x\to +\infty$, the questions of where the maximum occurs, and what it is, are natural.

And, as it happens, the computation is accessible in human terms. Namely, look for a critical point $x_o$, that is, where $f'(x_o)=0$. This condition is $$ 0\;=\;{1\over x}{1\over x^\varepsilon}-\varepsilon\cdot {\log x\over x^{\varepsilon+1}} \;=\; {1-\varepsilon\cdot \log x \over x^{\varepsilon+1}} $$ Thus, the maximum occurs where $\log x = 1/\varepsilon$. The value is easy to figure out, also.