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?
Interpretation of $f(n) \in o(n)$
2
$\begingroup$
asymptotics
-
0@bartgol: yes exactly. – 2012-07-15
1 Answers
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.
-
0You're right, there should be an absolute value there. – 2012-07-16