# Lower bound for comparison algorithm - checking whether permutation is odd or even

I consider problem: proving lower bound for comparison algorithm that check whether permutation is odd or even.
I know that this bound is $\Omega(n\lg n)$.

Could you give me a clue ?

• The lower bound would be $\Omega(n\log n)$. Nov 3, 2015 at 20:30
• Yes, you are right. Any clues ? Nov 3, 2015 at 20:41
• What are your thoughts? What approaches have you considered?
– D.W.
Nov 3, 2015 at 22:03
• It is solved, look below :) Nov 3, 2015 at 22:19

• Ok, I try to prove it. Let assume that order is not linear - it is only partial. Then exists $i < j$ such that we don't know which of them is greater. Then, if $a_i > a_j$ we have at least one additional inversion. So, before it was impossible to know parity of permutation. If $a_j < a_j$ there is no problem, however the crux is that we don't know order between $a_i$ and $a_j$. Conlusion is following: This problem requires at least comparisons as sorting algorithms, so $\Omega (n\lg n)$. What about this argument ? Nov 3, 2015 at 21:04
• Moreover, we may say that lower bound for counting number of inversions (comparison algorithm) is $\Omega (n\lg n)$ Nov 3, 2015 at 21:42