TAOCP 6.1 Exercise 10

Let $p_1, p_2, \dots, p_N$ be the probabilities that the argument equals $K_1, K_2, \dots, K_N$, with $\sum_{i=1}^N p_i = 1$.

taocpmathematicsalgorithmsvolume-3math-medium

Section 6.1: Sequential Searching

Exercise 10. [M20] [M20] The best arrangement of records in a sequential table is specified by (4); what is the worst arrangement? Show that the average number of comparisons in the worst arrangement has a simple relation to the average number of comparisons in the best arrangement.

Verified: yes
Solve time: 1m09s

Solution

Let $p_1, p_2, \dots, p_N$ be the probabilities that the argument equals $K_1, K_2, \dots, K_N$, with $\sum_{i=1}^N p_i = 1$. For any arrangement of the table, the average number of comparisons in a successful search is

$$ C = \sum_{i=1}^N i,p_i. $$

The best arrangement is given in (4), where the probabilities are ordered

$$ p_1 \ge p_2 \ge \cdots \ge p_N, $$

so that larger probabilities receive smaller indices.

To determine the worst arrangement, consider any permutation $\pi$ of ${1,\dots,N}$. The corresponding average number of comparisons is

$$ C(\pi) = \sum_{i=1}^N i,p_{\pi(i)}. $$

Let $\pi_{\min}$ be a permutation that minimizes $C(\pi)$. By the rearrangement inequality applied to the increasing sequence $1,2,\dots,N$, the sum is minimized when the largest probabilities are paired with the smallest indices, hence $\pi_{\min}$ is the identity permutation after sorting probabilities in decreasing order, which yields (4).

Similarly, the sum is maximized when the largest probabilities are paired with the largest indices. This occurs when the probabilities are arranged in the reverse order

$$ p_1 \le p_2 \le \cdots \le p_N. $$

Assume the best arrangement is indexed so that $p_1 \ge \cdots \ge p_N$. The worst arrangement is then obtained by reversing this order, so that the probability in position $i$ is $p_{N+1-i}$. The corresponding average number of comparisons is

$$ C_{\mathrm{worst}} = \sum_{i=1}^N i,p_{N+1-i}. $$

Substituting $j = N+1-i$, so $i = N+1-j$, gives

$$ C_{\mathrm{worst}} = \sum_{j=1}^N (N+1-j)p_j = (N+1)\sum_{j=1}^N p_j - \sum_{j=1}^N j p_j. $$

Using $\sum_{j=1}^N p_j = 1$ and $C_{\mathrm{best}} = \sum_{j=1}^N j p_j$, this simplifies to

$$ C_{\mathrm{worst}} = (N+1) - C_{\mathrm{best}}. $$

Thus the worst arrangement is the reverse ordering of the best arrangement, and its average number of comparisons satisfies a direct linear relation with the optimal value.

This completes the proof. ∎