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
    Try multiplying two functions from different "growth classes".2012-12-02
  • 0
    Related: can you find a function which is $O(n^{\varepsilon})$ for all positive $\varepsilon$ but is not $O(1)$?2012-12-02
  • 0
    I was trying to approach this way, but failed.2012-12-02
  • 0
    Well, what were you trying?2012-12-02
  • 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
    Try to prove it, if necessary :)2012-12-02
  • 0
    I can see now, the answer is $f(n)=n^{1+\log n}$ it was simpler than I thought.2012-12-02
  • 0
    @xan, that function is not $O(n^{1+\epsilon})$ for all $\epsilon > 0$.2012-12-02
  • 0
    $n\log n$ the solution is2012-12-02
  • 0
    @xan, there you go :)2012-12-02