Take the 2-minute tour ×

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

share|improve this question
Whoops, I mixed up f and g :) –  Ilya Jan 28 '13 at 2:49
I don't really understand the question after "However". Can you explain? –  GYC Jan 28 '13 at 2:56
I've updated the question. I hope I'm not too confused. –  Ilya Jan 28 '13 at 3:05

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
Thanks! This helps. –  Ilya Jan 28 '13 at 3:14

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

share|improve this answer
What I meant is that not only f(n) >= g(n) for some n, but f(n)=M so that g(n)<=M and g(x)<=M for all x. –  Ilya Jan 28 '13 at 3:11
I see. Updated. Hopefully you can figure it out. –  Bombyx mori Jan 28 '13 at 3:17

Your Answer


