TITLE: Does little-o notation imply going into infinity?
QUESTION [1 upvotes]: Let $f(n)=o(g(n))$. By definition there exists $n_0$ so that for all $n>n_0$ it holds that $\varepsilon \cdot g(n) \geq f(n)$ for $\varepsilon>0$ however small.
So, in plain language, starting from a certain point, $g(n)$ grows significantly faster than $f(n)$. However, how about the part before asymptotic behaviour kicks in, when $f(n)$ and $g(n)$ can go wild?
Is it possible that for some $x\in[0..n_0]$, $f(x)=M$ gets a maximal value so that $g(n) < M$ (for all $n$)?

REPLY [1 votes]: Yes for example, $f(x) = \frac{1}{x}$ defined  on $[\frac{1}{2},\infty)$ is $o(1)$ and $\forall x \in [\frac{1}{2},1):  \frac{1}{x} > 1$, and $f(x)$ reaches maximal value: $2$.

REPLY [0 votes]: I think you are confused. The little $o$ notation just means $|\frac{f(n)}{g(n)}|<\epsilon$ for any $\epsilon>0$ if $n$ is large enough. So it is totally possible that for some $n$ value $f(n)\ge g(n)$. For example $\sin[1/x]=o(x^{2})$.
{"set_name": "stack_exchange", "score": 1, "question_id": 288559}