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?
Asked
Active
Viewed 69 times
2
-
1Try $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
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.
bartgol
- 6,231
-
1Technically 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
-