In my study of complexity theory I encountered the following question: give an example of a function that is $\mathcal O ( n^{1+\varepsilon}))$. I have two questions:
$(1)$ Would $f(n) = n^{1+1/n}$ suffice? Because if we let $N = \varepsilon^{-1}$ in the definition of $\mathcal (\cdot)$, is seems to work.
$(2)$ Are there more functions that would suffice? Like $\log n$?
In theory $f(n)=n$ would also suffice, since it's $O(n)$ so also $O(n^{1+\varepsilon})$.
1) Note that $n^{1/n} = O(1)$. It is limited and always smaller than $e^{1/e}$ if i recall properly. Try to plot $x^{1/x}$ and you'll see it.
A more interesting example would be a function such that $f(n)/n \rightarrow \infty$, and $f(n)=O(n^{1+\varepsilon})$.
For instance $f(n)=n\log (n)$.
