Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

Thanks!

share|improve this question

1 Answer 1

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|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
1  
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

 
discard

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.