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

I need your help with the following statement:

Show there exist two function $f(n), g(n)$ such that meet the following definition:

$g(n) = O(f(n))$ and $f(n) \ne O(g(n))$

But don't meet the little-o definition, that is :

Not for every $\epsilon >0$ there exist $n_0 \ge 1$ such that $g(n) \le \epsilon f(n)$ for every $n \ge n_0$

I'm not sure what way should I pick here.

It seems like every "Normal" two functions which meets the first definition also meets the little-o definition.

Thanks in advance!

share|cite|improve this question
up vote 1 down vote accepted

Just think of two functions $f$ and $g$, which are more or less "equal", but one of them (here: $g$) is to oszillating to bound the other. For example $f(n) = 1$ and $g(n) = \sin(n) + 1$.

share|cite|improve this answer
So actually I'm taking advantage of the Big-O being "Partially ordered set". That is, using the missing property "Totality". Am I right? – SyndicatorBBB Nov 6 '12 at 13:32
The failure of "Totality" says that there are functions $f, g$ with $f \not\in O(g)$, $g \not\in O(f)$. – martini Nov 6 '12 at 13:41
Yes sorry my mistake, I was confused. I think I understand now. You chose a function g(n) such that in the infinity will be 0 or 1 (oscillating) and therefore the little-o definition doesn't apply. – SyndicatorBBB Nov 6 '12 at 13:45

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.