Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 1 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.