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$
$\endgroup$
4
-
$\begingroup$ The lower bound would be $\Omega(n\log n)$. $\endgroup$– Yuval FilmusNov 3, 2015 at 20:30
-
$\begingroup$ Yes, you are right. Any clues ? $\endgroup$– user40545Nov 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$– user40545Nov 3, 2015 at 22:19
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
answered Nov 3, 2015 at 20:41
-
$\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$ Nov 3, 2015 at 21:04
-
1
-
$\begingroup$ Thanks you very much! It seemed to be difficult. In real it is easy! $\endgroup$ 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$ Nov 3, 2015 at 21:42