Let $O(n)$ be Big-O of $n$ and $o(n)$ be Small-O of $n$.It is a well-known fact that $O(n \log{n}) \subset O(n^{1 + \epsilon})$ for any $\epsilon > 0$. Can we omit the $\epsilon$, and just type $O(n \log{n}) \subset O(n^{1 + o(1)})$?
Is $\log{n}$ bounded from above by $n^{o(1)}$?
asymptotics;landau notation
Consider the function $f(n) = n^{1 + \frac{1}{n}}$ which I guess you'd say is in $O(n^{1 + o(1)})$. I'm not sure you can call it polynomial, though.Now, compute$\qquad \displaystyle \lim_{n \to \infty} \frac{n^{1 + \frac{1}{n}}}{n \log n} = 0$,so you have in fact that $f \in o(n \log n)$. Therefore, functions in this funky class of yours are not even (all) asymptotic upper bounds for $n \log n$.The difference is that $\varepsilon$ ensures a non-vanishing distance from $n^1$ whereas $o(1)$ means that functions of the form $n^{1 + o(1)}$ in fact converge towards $n \in o(n \log n)$.