2
$\begingroup$

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 ?

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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\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, 2015 at 21:04
  • 1
    $\begingroup$ That's the idea. $\endgroup$ Nov 3, 2015 at 21:08
  • $\begingroup$ Thanks you very much! It seemed to be difficult. In real it is easy! $\endgroup$
    – user40545
    Nov 3, 2015 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, 2015 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.