1
$\begingroup$

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!

1 Answers 1

0

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

  • 0
    If I take the witeness to be c=1 and n0 = 1 this formula won't work. Am I right?2012-11-03
  • 1
    You are right but this is beside the point since one cannot **choose** a witness pair.2012-11-03
  • 0
    Understood, thank you!2012-11-03