TAOCP 5.3.1 Exercise 29

We model the algorithm as a binary decision tree $T$.

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.3.1: Minimum-Comparison Sorting

Exercise 29. [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: no
Solve time: 8m42s

Solution

We model the algorithm as a binary decision tree $T$. Each internal node of $T$ is labeled with a comparison $a_i:a_j$ ($1\le i<j\le n$). The left branch is followed when $a_i<a_j$, the right branch when $a_i>a_j$. Each leaf of $T$ is labeled “even” or “odd”, indicating the output of the algorithm. For a permutation $\pi = a_1a_2\ldots a_n$, the path from the root to the leaf reached by $\pi$ corresponds to the sequence of comparison outcomes; let $E_L$ be the set of comparisons made along this path, with their outcomes.

The outcomes define a partial order $P_L$ on the set ${1,2,\ldots,n}$: $i<j$ in $P_L$ iff the comparison $a_i:a_j$ was made and the outcome was $a_i<a_j$ (or $a_j:a_i$ with outcome $a_j>a_i$). The permutations that reach leaf $L$ are exactly the linear extensions of $P_L$. For the algorithm to be correct, all linear extensions of $P_L$ must have the same parity (all even or all odd); otherwise $L$ could not be consistently labeled.

Let $G_L=(V,E_L)$ be the undirected graph whose vertices are the $n$ elements and whose edges are the pairs compared along the path to $L$. If $|E_L| < n-1$, then $G_L$ is disconnected; thus $P_L$ has at least two connected components, say $C_1$ and $C_2$. Because no comparison relates an element of $C_1$ to an element of $C_2$, every linear extension of $P_L$ is obtained by interleaving a linear extension of $C_1$ with a linear extension of $C_2$ (and the other components).

Fix linear extensions $\sigma_1$ of $C_1$ and $\sigma_2$ of $C_2$. Let $x$ be the first element of $\sigma_1$ and $y$ be any element of $C_2$. Consider the following two linear extensions of $P_L$:

  1. $\sigma_1$ followed by $\sigma_2$ (all of $C_1$ before all of $C_2$);
  2. $y$ followed by $\sigma_1$ followed by the rest of $\sigma_2$ (place $y$ immediately before $x$).

These two are valid because there are no constraints between $C_1$ and $C_2$. They differ only by the transposition of the adjacent elements $y$ and $x$; hence their inversion counts differ by $1$, so their parities are opposite. Therefore $P_L$ admits both an even and an odd linear extension.

Consequently, for the algorithm to be correct, every leaf $L$ must satisfy $|E_L|\ge n-1$. Thus the depth of $T$,the maximum number of comparisons made on any path,is at least $n-1$.

This completes the proof. ∎

Notes

The bound $n-1$ is derived from the simple graph-theoretic fact that a connected graph on $n$ vertices has at least $n-1$ edges. The information-theoretic lower bound for this problem is $\lceil\lg(n!/2)\rceil \approx n\lg n$, which is much larger for $n\ge 4$; the exercise asks for the elementary argument that yields a linear bound. The exact minimum number of comparisons required to determine the parity of a permutation is known to be $n-1$ when $n$ is not a power of $2$, and $n$ when $n$ is a power of $2$ (S. M. Chase, J. ACM 13 (1966), 310-313).