TAOCP 5.2.3 Exercise 2

For the input $N,N-1,\ldots,2,1$, the sequence $K_1, K_2, \ldots, K_j$ is strictly decreasing for every $j \ge 2$.

taocpmathematicsalgorithmsvolume-3

Section 5.2.3: Sorting by Selection

Exercise 2. [**] [20] What is the value of the quantity B in the analysis of Program S, when the input is N...321?

Verified: yes
Solve time: 1m27s

For the input $N,N-1,\ldots,2,1$, the sequence $K_1, K_2, \ldots, K_j$ is strictly decreasing for every $j \ge 2$. In step $S2$, when processing index $j$, the algorithm initializes $rA \leftarrow K_j$ and then scans $k = j-1, j-2, \ldots, 1$. Since $K_j$ is the smallest element of $K_1,\ldots,K_j$, every comparison $K_i > K_k$ is satisfied at the first check involving each $K_k$, and each such occurrence triggers exactly one change of the current right-to-left maximum via the assignments in steps $07$–$08$.

For fixed $j$, this produces one update for each $k = j-1, j-2, \ldots, 1$, hence exactly $j-1$ changes. Summing over all $j$ yields

$$ B = \sum_{j=2}^N (j-1) = \sum_{m=1}^{N-1} m = \frac{N(N-1)}{2}. $$

Thus

$$ \boxed{B = \frac{N(N-1)}{2}}. $$