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 ?

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

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.

| cite | improve this answer | |
  • $\begingroup$ 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 ? $\endgroup$ – user40545 Nov 3 '15 at 21:04
  • 1
    $\begingroup$ That's the idea. $\endgroup$ – Yuval Filmus Nov 3 '15 at 21:08
  • $\begingroup$ Thanks you very much! It seemed to be difficult. In real it is easy! $\endgroup$ – user40545 Nov 3 '15 at 21:23
  • $\begingroup$ Moreover, we may say that lower bound for counting number of inversions (comparison algorithm) is $\Omega (n\lg n)$ $\endgroup$ – user40545 Nov 3 '15 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.