Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
Problem Detail: 

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 ?

Asked By : user40545
Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback