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 ?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
Hint: Show that if you know the parity of the input permutation then you know the entire permutation, and so you can sort the list.
In more detail, the information that you have at any leaf of the decision tree can be represented as a partial order on the elements. Show that if this partial order is not linear then it has a linear completion which is an odd permutation and another linear completion which is an even permutation.