2
$\begingroup$

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?

  • 0
    @bartgol: yes exactly.2012-07-15

1 Answers 1

3

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.

  • 0
    You're right, there should be an absolute value there.2012-07-16