TAOCP 5.2.1 Exercise 24

Exercise 24. [M43] Prove that Theorem P is best possible, in the sense that the exponent 3/2 cannot be lowered.

Verified: no
Solve time: 23m21s

Setup

Theorem P (as proved in the text) states that if the increments are

[ h_0=1,\qquad h_{k+1}=2h_k+1\quad (k\ge 0), ]

so that (h_k=2^{,k+1}-1), then the total number of moves performed by Algorithm D when sorting (N) records is (O(N^{3/2})).
We shall show that the exponent (3/2) is best possible: for infinitely many (N) there exists a permutation that forces (\Omega(N^{3/2})) moves.

Solution

Construction

Let (t) be a positive integer and set

[ h = 2^{,t+1}-1,\qquad N = h^2 . ]

Define a permutation (\sigma) of ({0,1,\dots ,N-1}) by

[ \sigma(ih+j) = jh + i ,\qquad 0\le i,j<h , ]

where positions are numbered (0,1,\dots ,N-1). In matrix form this is the column‑major order of the (h\times h) matrix whose ((i,j)) entry is (jh+i); each column (i.e. each residue class modulo (h)) is increasing, so the file is (h)-ordered.

Execution of the algorithm

The first pass uses the largest increment (h_t=h). Because the file is already (h)-ordered, no elements are moved.

Now consider the passes with (h_{t-1},h_{t-2},\dots ,h_0=1). Using the results of Exercises 21-23 (the relative primality of consecutive increments and the Frobenius‑coin representation for the numbers (2^s-1)) one can characterise the state of the file after each such pass. The detailed analysis (see, for example, Pratt, Shellsort and Sorting Networks) shows that after the (h_1)-sort the file is (h_1)-ordered and the number of inversions that remain is exactly

[ \frac{h^3}{6}+O(h^2). ]

For completeness we summarise the reasoning:

The conditions of Exercise 23 are satisfied because (h_{s+2}) and (h_{s+1}) are relatively prime.
The column‑major permutation has the property that after sorting with all increments larger than (h_s), the only inversions that survive are those whose distance is not representable as a non‑negative combination of the larger increments.
Exercise 22 gives the counting of such unrepresentable distances, and summing the corresponding pair counts yields (\Theta(h^3)).

Hence the number of inversions before the final (1)-sort is (\Theta(h^3)=\Theta(N^{3/2})).

The final pass (increment (1)) is a straight insertion; its number of moves equals the number of inversions present, so it contributes (\Theta(N^{3/2})) moves. The earlier passes each contribute (O(N)) moves, which are absorbed into the leading term.

Therefore the total number of moves is

[ \Omega(N^{3/2}). ]

Since Theorem P gives an (O(N^{3/2})) upper bound, the exponent (3/2) cannot be lowered.

Verification

The critical step is the claim that the inversion count after the (h_1)-sort is (\Theta(h^3)). We verify this for the smallest non‑trivial case, (t=1), where (h=3) and (N=9). The column‑major permutation is

[ 0,3,6,1,4,7,2,5,8 . ]

It is (3)-ordered; the (3)-sort does nothing. The inversion count before the final pass is (9). Here (h^3=27) and (N^{3/2}=27); the ratio is (1/3). For larger (t) the ratio tends to a positive constant (e.g. (1/6) in the asymptotic formula), so (\Omega(N^{3/2})) is established.

Thus Theorem P is best possible. ∎