1

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$)?

Ilya
  • 273

2 Answers2

1

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$.

Rustyn
  • 8,407
0

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})$.

Bombyx mori
  • 19,638
  • 6
  • 52
  • 112