TAOCP 5.2.1 Exercise 19
Let the increments be \(h_{t-1}>h_{t-2}>\cdots>h_0=1\) and assume they satisfy the divisibility condition \[ h_{s}\;\text{is a multiple of}\;h_{s-1}\qquad(1\le s\le t-1).
Section 5.2.1: Sorting by Insertion
Exercise 19. ▶ [M25] What is the average value of the quantity $A$ in the timing analysis of Program D, when the increments satisfy the divisibility condition (5)?
Verified: no
Solve time: 20m21s
Solution
Let the increments be (h_{t-1}>h_{t-2}>\cdots>h_0=1) and assume they satisfy the divisibility condition
[ h_{s};\text{is a multiple of};h_{s-1}\qquad(1\le s\le t-1). ]
In Algorithm D the quantity (A) is the total number of times the inner loop exits because the index (i) becomes (\le0); this is exactly the sum over all passes of [ (\text{number of left‑to‑right minima in an }h_s\text{-subsequence})-1, ] since the first element of each subsequence is a left‑to‑right minimum that is never inserted.
1. Pass with the largest increment (h_{t-1})
The input permutation is random. An (h_{t-1})-subsequence has size (m=N/h_{t-1}) (for simplicity assume (N) is a multiple of every increment; otherwise the size varies and the first term should be written as a sum of harmonic numbers with ceilings). In a random permutation of (m) elements the expected number of left‑to‑right minima is (H_m). There are (h_{t-1}) such subsequences, hence
[ \mathrm{E}[A_{t-1}] = h_{t-1}\bigl(H_{N/h_{t-1}}-1\bigr). ]
2. Later passes ((s=t-2,\dots ,0))
After the pass with increment (h_{s+1}) the array is (h_{s+1})-sorted, so every (h_{s+1})-subsequence is sorted. Because (h_{s+1}) is a multiple of (h_s), write
[ r = \frac{h_{s+1}}{h_s}. ]
An (h_s)-subsequence is formed by interleaving (r) sorted lists (the (h_{s+1})-subsequences) in round‑robin order: the first element of each list, then the second element of each list, and so on. Let the first elements of the (r) lists be
[ a_1,a_2,\dots ,a_r ]
in the order they appear. Each list is sorted, so for (k>1) the (k)-th element of a list is larger than its first element (a_j) and appears later in the (h_s)-subsequence. Consequently only the first (r) elements of the (h_s)-subsequence can be left‑to‑right minima; all later elements are blocked by their own list’s first element.
Now examine the minima of the (h_{s+1})-subsequences. After pass (s+1) these minima occupy positions (1,2,\dots ,h_{s+1}) (the first element of each sorted (h_{s+1})-subsequence). Because the initial permutation is random and the algorithm is deterministic, the values at those positions are a uniformly random permutation of (h_{s+1}) distinct keys. Therefore, for a fixed (h_s)-subsequence the (r) first elements (a_1,\dots ,a_r) are a random permutation of (r) distinct numbers. The expected number of left‑to‑right minima among them is (H_r).
Hence the expected number of left‑to‑right minima in the whole (h_s)-subsequence is (H_r). Subtracting the first element (which is not inserted) gives the expected contribution to (A) from that subsequence:
[ \mathrm{E}[A_s^{\text{(one subsequence)}}] = H_r - 1. ]
There are (h_s) such subsequences, so
[ \mathrm{E}[A_s] = h_s,(H_r-1) = h_s\bigl(H_{h_{s+1}/h_s}-1\bigr). ]
The argument does not require the lists to be of equal length; it only needs each list to have at least one element, which is true because (h_{s+1}\le N).
3. Sum over all passes
[ \mathrm{E}[A] = h_{t-1}\bigl(H_{N/h_{t-1}}-1\bigr) ;+; \sum_{s=0}^{t-2} h_s\bigl(H_{h_{s+1}/h_s}-1\bigr). ]
When (N) is a multiple of all increments we may introduce (h_t=N) and write the compact expression
[ \boxed{\displaystyle\mathrm{E}[A] = \sum_{s=0}^{t-1} h_s\bigl(H_{h_{s+1}/h_s}-1\bigr)} , ]
where (h_0=1) and (h_t=N). For the special case (t=1) (straight insertion) this reduces to (1,(H_N-1)=H_N-1), the well‑known average value of (A).
If (N) is not a multiple of (h_{t-1}) the first term should be replaced by (\sum_{i=1}^{h_{t-1}}\bigl(H_{\lceil (N-i)/h_{t-1}\rceil+1}-1\bigr)); the remaining terms are unchanged because they depend only on the increments and not on (N).∎