TAOCP 6.1 Exercise 19

Section 6.1: Sequential Searching

Exercise 19. [M20] [M20] Continuing exercise 18, what are the optimal arrangements for catenated searches when the function d(i,7) has the property that d(i,j) + d(j,i) = c for all i 7? [This situation occurs, for example, on tapes without read-backwards capability, when we do not know the appropriate direction to search; for i < j we have, say, d(i,j) = a+b(Ligit---+2Z,;) and d(j,i) = a+b(Lj41+---+0n)+r+b(Lit+:--+Li), where r is the rewind time.]

Verified: yes
Solve time: 1m09s

Solution

Let a fixed permutation of the records be given, and let $\pi(i)\in{1,\dots,N}$ denote the position of record $R_i$ in the array. From the model in Exercise 18, the average time is

$$ V=\sum_{i=1}^N\sum_{j=1}^N p_i p_j, d(\pi(i),\pi(j)). $$

Split the sum into diagonal and off-diagonal parts. Since $d(\pi(i),\pi(i))$ corresponds to no movement in a search that starts and ends at the same position, it contributes a constant independent of the permutation, so only $i\ne j$ affects comparisons between arrangements:

$$ V=\sum_{i\ne j} p_i p_j, d(\pi(i),\pi(j)) + \text{constant}. $$

For each unordered pair ${i,j}$ with $i\ne j$, exactly two ordered terms appear:

$$ p_i p_j, d(\pi(i),\pi(j)) \quad\text{and}\quad p_j p_i, d(\pi(j),\pi(i)). $$

Since $p_i p_j=p_j p_i$, their combined contribution is

$$ p_i p_j\bigl(d(\pi(i),\pi(j)) + d(\pi(j),\pi(i))\bigr). $$

The hypothesis states that for all positions $a,b$,

$$ d(a,b)+d(b,a)=c. $$

Applying this with $a=\pi(i)$ and $b=\pi(j)$ gives

$$ d(\pi(i),\pi(j)) + d(\pi(j),\pi(i)) = c, $$

hence each unordered pair ${i,j}$ contributes exactly

$$ c, p_i p_j. $$

Therefore,

$$ V=\sum_{1\le i<j\le N} c, p_i p_j + \text{constant} = c\sum_{1\le i<j\le N} p_i p_j + \text{constant}. $$

The expression $\sum_{1\le i<j\le N} p_i p_j$ depends only on the probability distribution and not on the permutation of the records. Hence $V$ is independent of the ordering of the table.

Since every arrangement yields the same value of $V$, no permutation can improve upon another, and every ordering is optimal. This completes the proof. ∎