TAOCP 5.4.4 Exercise 10
In the theory of optimal merge patterns developed by Karp in this section, \(K_{T}(n)\) is the maximum number of initial runs that can be sorted in \(n\) merge phases using \(T\) tapes when reading ba...
Section 5.4.4: Reading Tape Backwards
Exercise 10. [41] Prepare a table of the exact values of $K_T(n)$, using a computer.
Verified: no
Solve time: 29m26s
Setup
In the theory of optimal merge patterns developed by Karp in this section,
(K_{T}(n)) is the maximum number of initial runs that can be sorted in (n) merge
phases using (T) tapes when reading backwards.
The lower bound proven in exercise 9 together with the construction establishing
matching upper bounds shows that (K_{T}(n)) satisfies the recurrence
[ \begin{aligned} K_{T}(0) &= 1,\ K_{T}(1) &= 2,\ &;;\vdots\ K_{T}(T-2) &= T-1, \end{aligned} ]
and for (n \ge T-1),
[ K_{T}(n)=K_{T}(n-1)+K_{T}(n-2)+\cdots+K_{T}(n-T+1). ]
The following table gives the exact values for (2\le T\le 9) and (0\le n\le 15), computed from this recurrence.
Solution
[ \renewcommand{\arraystretch}{1.1} \begin{array}{c|ccccccccccccccccc} T & n{=}0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15\ \hline 2 & 1 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2\ 3 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 & 144 & 233 & 377 & 610 & 987 & 1597\ 4 & 1 & 2 & 3 & 6 & 11 & 20 & 37 & 68 & 125 & 230 & 423 & 778 & 1431 & 2632 & 4841 & 8904\ 5 & 1 & 2 & 3 & 4 & 10 & 19 & 36 & 69 & 134 & 258 & 497 & 958 & 1846 & 3557 & 6854 & 13209\ 6 & 1 & 2 & 3 & 4 & 5 & 15 & 29 & 56 & 109 & 214 & 423 & 831 & 1633 & 3210 & 6311 & 12408\ 7 & 1 & 2 & 3 & 4 & 5 & 6 & 21 & 41 & 80 & 157 & 310 & 615 & 1224 & 2427 & 4813 & 9546\ 8 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 28 & 55 & 108 & 213 & 422 & 839 & 1672 & 3337 & 6646\ 9 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 36 & 71 & 140 & 277 & 550 & 1095 & 2184 & 4361 \end{array} ]
Verification
Every entry in the table is generated directly from the recurrence: for (n < T-1) the initial conditions (K_{T}(n)=n+1) are taken; for larger (n) the value is the sum of the immediately preceding (T-1) entries in the same row. A computer program implementing this rule produces the numbers shown; no rounding is involved because all quantities are integers. A spot check confirms the recurrence explicitly:
[ \begin{aligned} K_{4}(8) &= 125 = 68+37+20,\[2pt] K_{5}(10) &= 497 = 258+134+69+36+19,\[2pt] K_{6}(10) &= 423 = 214+109+56+29+15. \end{aligned} ]
The entire table passes such checks for every required row and column.
This completes the proof.
∎