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

Suppose that some function $f(n)$ is in $o(n)$. Is it fomally correct to say that there exists an $N$ such that for all $n \ge N$ it holds that $$f(n) \le \frac{c n}{g(n)}$$ where $c>0$ is a constant and $g(n)$ is a strictly increasing function of $n$ ? My reasoning is that $f(n) \in o(n)$ implies that $\lim_{n\rightarrow\infty} \frac{f(n)}{n} = 0$, so the above should follow directly from $f(n) \in o(n)$, right?

share|cite|improve this question
Try $g(n) = (1 - 1/n) \inf \{k / f(k) : k \geq n\}$ (unless $g$ is identically equal to 0 starting from some $N$). – Yury Jul 15 '12 at 16:32
Just to be clear: you want to prove that there is at least one such $g(n)$? – bartgol Jul 15 '12 at 16:33
@bartgol: yes exactly. – somebody Jul 15 '12 at 16:37
up vote 3 down vote accepted

You can reformulate your question as: is it true that if $f(n)\to 0$, then there is an increasing function $g(n)$ such that for $n$ large enough $f(n)\leq c/g(n)$? I think the answer to this question is positive. As Yury pointed out, it should be enough to take $$g(n)=h(n)\text{inf}\left\{\frac{1}{f(k)},k\geq n\right\}$$ where $h(n)$ is any positive increasing function smaller than one.

share|cite|improve this answer
Technically it should be $|f(k)|$ rather than $f(k)$, since $f(n)$ was not specified to be positive. Indeed, not only is your $g(n)$ increasing, it increases to infinity. By adding this clause, the condition becomes exactly equivalent to $f(n) = o(n)$. – Erick Wong Jul 15 '12 at 17:05
You're right, there should be an absolute value there. – bartgol Jul 16 '12 at 18:30

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.