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

For all $\epsilon$ we have that $f(n)\le \epsilon n$ where n is a natural number. What can we say about the growth of $f(n)$? Clearly $f(n)=O(n)$, can we say anything sharper?

share|cite|improve this question
If you mean for all $\epsilon>0$, then $f(n)\le 0$ for each $n$. – David Mitra May 6 '12 at 0:18
Gee, $f(n)$ is small. Stunted, even. I guess that is not nice to say. Size challenged, that sounds good. – André Nicolas May 6 '12 at 0:22
For reference, the difference between what you've written and saying that $f(n)\in o(n)$ is that the latter just says that for each $\epsilon$ there's some $n_0$ s.t. $f(n)\leq\epsilon n$ for all $n\gt n_0$ (small caveat: for positive $f$); your condition says that this we could take $n_0=1$ for all $\epsilon$, and that as David notes, that implies (again, assuming non-negativity of $f$) that $f$ is identically zero. – Steven Stadnicki May 6 '12 at 0:23
@Steven: I think the OP is looking for $f(n) \in o(n)$, so you may want to add it as an answer. – TMM May 6 '12 at 0:29
If f is a real-valued function then all we can say is that f(n) = 0 for all n, and nothing else. If f is a natural-number-values function, then simply f(n) = 0 for all n. – Adam Rubinson May 6 '12 at 0:30

Your Answer


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

Browse other questions tagged or ask your own question.