How close is $n $ to $ n \log n$? 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}$
 A: 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$).
A: 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$.
A: 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.
