TAOCP 5.3.1 Exercise 7
Let the computation be represented by a binary comparison tree.
Section 5.3.1: Minimum-Comparison Sorting
Exercise 7. [M25] [M25] (S. M. Chase.) Let $a_1, a_2, \ldots, a_n$ be a permutation of ${1, 2, \ldots, n}$. Prove that any algorithm that decides whether this permutation is even or odd (that is, whether it has an even or odd number of inversions), based solely on comparisons between the $a$'s, must make at least $n \lg n$ comparisons, even though the algorithm has only two possible outcomes.
Verified: yes
Solve time: 2m41s
Let the computation be represented by a binary comparison tree. Each internal node compares $a_i$ and $a_j$, and each leaf corresponds to a set $P(v)$ of permutations consistent with the outcomes along the root-to-leaf path.
Each comparison outcome imposes a constraint of the form $a_i < a_j$ or $a_i > a_j$. Hence $P(v)$ is exactly the set of linear extensions of a partial order $R_v$ on ${1,\dots,n}$, where $i <_{R_v} j$ means that the path has established $a_i < a_j$.
We prove first a structural lemma about such leaves.
Lemma
If $R_v$ is not a total order, then $P(v)$ contains two permutations of opposite parity.
Proof
Assume $R_v$ is not total. Then there exist distinct elements $p,q \in {1,\dots,n}$ that are incomparable in $R_v$.
We show that there exist two linear extensions of $R_v$ that differ by swapping two adjacent elements $p$ and $q$.
A standard fact about partial orders is that if two elements are incomparable, then there exists a linear extension in which they appear consecutively. Concretely, take any linear extension of $R_v$. If $p$ appears before $q$ but they are not adjacent, repeatedly swap adjacent elements that are not constrained by $R_v$ to move $p$ rightward until it is immediately before $q$. None of these swaps violates $R_v$, since each swap exchanges adjacent elements that are incomparable in $R_v$ at that moment. Thus we obtain a linear extension of $R_v$ in which $p$ and $q$ are adjacent.
Let this linear extension be
$$ (\dots, p, q, \dots). $$
Define a second permutation by swapping these adjacent elements:
$$ (\dots, q, p, \dots). $$
Since $p$ and $q$ are incomparable in $R_v$, neither order is forbidden, so both permutations remain linear extensions of $R_v$.
Now compare inversion parity. The two permutations are identical except for the transposition of adjacent elements $p$ and $q$. This changes the inversion count by exactly $1$, since the only inversion whose status changes is the pair $(p,q)$. Therefore the two permutations have opposite parity.
Hence $P(v)$ contains both even and odd permutations. ∎
Consequence: structure of leaves
For the algorithm to be correct, every leaf must output a single parity value. Therefore no leaf can contain both an even and an odd permutation. By the lemma, this implies that $R_v$ must be a total order at every leaf.
Thus each leaf corresponds to a complete ordering of $a_1,\dots,a_n$, and hence to a unique permutation of ${1,\dots,n}$.
So the comparison tree must have at least $n!$ leaves.
Depth lower bound
A binary tree of height $h$ has at most $2^h$ leaves. Therefore
$$ 2^h \ge n!, \quad \text{so} \quad h \ge \log_2(n!). $$
Using Stirling’s approximation,
$$ \log_2(n!) = \Theta(n \log n), $$
more precisely,
$$ \log_2(n!) \ge n \log_2 n - O(n). $$
Hence any comparison-based algorithm deciding the parity of a permutation requires at least $n \log n$ comparisons in the worst case.
∎