# Find an example of function

Find an example of a function $f$ such that satisfies: $$\forall_{\varepsilon>0} \ f(n)=O(n^{1+\varepsilon})$$ but not $$f(n)=O(n)$$

I had been thinking about it for an hour and still can't find it. Can anybody help?

-
Try multiplying two functions from different "growth classes". – Antonio Vargas Dec 2 '12 at 15:16
Related: can you find a function which is $O(n^{\varepsilon})$ for all positive $\varepsilon$ but is not $O(1)$? – WimC Dec 2 '12 at 15:22
I was trying to approach this way, but failed. – xan Dec 2 '12 at 15:26
Well, what were you trying? – Antonio Vargas Dec 2 '12 at 15:30
Like WimC said I was trying to approach. For example $n^{1/n}=O(n^{\varepsilon})$ for every $\varepsilon$, unfortunately it's also $O(1)$. – xan Dec 2 '12 at 15:33

Hint: $\log n = O(n^{\epsilon})$ for all $\epsilon > 0$.

-
Try to prove it, if necessary :) – Antonio Vargas Dec 2 '12 at 15:39
I can see now, the answer is $f(n)=n^{1+\log n}$ it was simpler than I thought. – xan Dec 2 '12 at 15:40
@xan, that function is not $O(n^{1+\epsilon})$ for all $\epsilon > 0$. – Antonio Vargas Dec 2 '12 at 15:44
$n\log n$ the solution is – xan Dec 2 '12 at 15:54
@xan, there you go :) – Antonio Vargas Dec 2 '12 at 15:54