Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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? – user123454321 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
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|cite|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|cite|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


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.