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
    Understood, thank you!2012-11-03