TAOCP 5.2.3 Exercise 1
For a fixed value of $j$, step S2 selects the maximum of the keys $K_1,\ldots,K_j$.
Section 5.2.3: Sorting by Selection
Exercise 1. [**] [M25] Step S3 of Algorithm S accomplishes nothing when i = j; is it a good idea to test whether or not i = j before doing step S3? What is the average number of times the condition i = j will occur in step S3 for random input?
Verified: yes
Solve time: 1m16s
For a fixed value of $j$, step S2 selects the maximum of the keys $K_1,\ldots,K_j$. In a random permutation, each of the $j$ positions is equally likely to contain this maximum, so the probability that the selected index $i$ equals $j$ is $1/j$. Since step S3 is executed once for each $j=2,3,\ldots,N$, the expected number of executions of S3 in which $i=j$ holds is
$$ \sum_{j=2}^{N} \frac{1}{j} = H_N - 1. $$$
Thus, on average, the condition $i=j$ occurs $H_N - 1$ times during step S3 over the full execution of Algorithm S.
Introducing an explicit test for $i=j$ before step S3 replaces each unconditional exchange attempt by a comparison followed, in rare cases, by skipping three assignments when $i=j$. The test is performed once for each of the $N-1$ iterations, so it introduces $N-1$ additional comparisons. The number of exchanges avoided is $H_N - 1$, and each avoided exchange saves the three assignments in lines 11 through 13. The total expected saving is therefore proportional to $3(H_N - 1)$ assignment operations, while the extra cost is proportional to $N-1$ comparisons. Since $H_N$ grows like $\log N$, the added linear cost dominates the logarithmic saving, and the modification does not improve the average running time.