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've just encountered a weird statement regarding the BigOmega operator.

I should prove that the BigOmega operator isn't totally ordered. As a prove hint, I should show that there are two functions, say f(n) and g(n) such that:

$f(n)\ne \Omega(g(n))$ and $g(n)\ne \Omega(f(n))$

I read about the subject Total order in Wikipedia and I found out that the propery I'm missing (trying to prove that It doesn't exist) is "totality".

Although I know what I should prove It seems impossible.

Also I believe It won't be simple function such as: $n, n^2$ but something related to $log$.

Can someone please give me an hint?


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

Try $f(n)=1$ if $n$ is even, $f(n)=0$ if $n$ is odd, and $g(n)=1-f(n)$ for every $n$.

share|cite|improve this answer
If I take the witeness to be c=1 and n0 = 1 this formula won't work. Am I right? – SyndicatorBBB Nov 3 '12 at 13:47
You are right but this is beside the point since one cannot choose a witness pair. – Did Nov 3 '12 at 13:57
Understood, thank you! – SyndicatorBBB Nov 3 '12 at 13:58

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.