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 ?
Lower bound for comparison algorithm - checking whether permutation is odd or even
algorithms;algorithm analysis;permutations
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.