0
$\begingroup$

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?

  • 0
    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)$.2012-12-02

1 Answers 1

1

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

  • 0
    @xan, there you go :)2012-12-02