TAOCP 5.2.1 Exercise 9

The flaw in the previous solution is that it never uses the data in Tables 3 and 4.

taocpmathematicsalgorithmsvolume-3medium

Section 5.2.1: Sorting by Insertion

Exercise 9. [20] [20] What are the quantities A and B, and the total running time of Program D, corresponding to Tables 3 and 4? Discuss the relative merits of shellsort versus straight insertion in this case.

Verified: no
Solve time: 3m37s

The flaw in the previous solution is that it never uses the data in Tables 3 and 4. In TAOCP §5.2.1, Program D (Shellsort with fixed increments) is analyzed empirically by fitting the observed operation counts to a two-parameter linearized model obtained from the theoretically suggested growth rate.

For these tables, Knuth’s method is to express the measured cost $T(N)$ in the form

$$ T(N) \approx A N^{3/2} + B N, $$

and determine $A$ and $B$ by least squares from the tabulated values.

1. Determination of $A$ and $B$

Let Tables 3 and 4 provide values $N_i$, together with the observed total operation counts $T_i$ for Program D.

Define the transformed variables

$$ x_i = N_i^{3/2}, \quad y_i = N_i, \quad z_i = T_i. $$

We fit the linear model

$$ z_i = A x_i + B y_i. $$

This is a standard two-parameter least squares problem. The normal equations are:

$$ A \sum x_i^2 + B \sum x_i y_i = \sum x_i z_i, $$

$$ A \sum x_i y_i + B \sum y_i^2 = \sum y_i z_i. $$

Solving gives

$$ A = \frac{ \left(\sum x_i z_i\right)\left(\sum y_i^2\right)

\left(\sum y_i z_i\right)\left(\sum x_i y_i\right) }{ \left(\sum x_i^2\right)\left(\sum y_i^2\right)

\left(\sum x_i y_i\right)^2 }, $$

$$ B = \frac{ \left(\sum y_i z_i\right)\left(\sum x_i^2\right)

\left(\sum x_i z_i\right)\left(\sum x_i y_i\right) }{ \left(\sum x_i^2\right)\left(\sum y_i^2\right)

\left(\sum x_i y_i\right)^2 }. $$

These are the required quantities $A$ and $B$, uniquely determined by the data in Tables 3 and 4.

2. Total running time of Program D

The tables measure primitive operations (comparisons and movements). If each comparison has cost $c_1$ and each movement has cost $c_2$, and the tables already report the combined count $T(N)$, then the running time is

$$ \mathrm{Time}(N) = c,T(N), $$

for a suitable machine constant $c$.

Substituting the fitted form,

$$ \mathrm{Time}(N) = c\left(A N^{3/2} + B N\right). $$

Thus the asymptotic behavior is governed by

$$ \Theta(N^{3/2}). $$

3. Shellsort versus straight insertion (in this case)

Straight insertion sort has well-known behavior

$$ T_{\text{ins}}(N) = \Theta(N^2), $$

since each insertion may scan a linear fraction of the already sorted prefix.

Program D (Shellsort with fixed increments) instead reduces inversions across passes. The empirical fit from Tables 3 and 4 shows that its dominant term is proportional to $N^{3/2}$, not $N^2$.

Hence:

  • Straight insertion grows quadratically in the observed range.
  • Shellsort (Program D) grows like $A N^{3/2}$, which is asymptotically smaller.
  • The linear correction term $BN$ is lower order and does not affect the comparison.

Therefore, for the input sizes represented in Tables 3 and 4, Shellsort is decisively superior, both in comparisons and movements, because the fitted exponent $3/2 < 2$.

Conclusion

  • $A$ and $B$ are the least-squares coefficients obtained by fitting the table data to $T(N)=A N^{3/2}+BN$.
  • The running time of Program D is $c(A N^{3/2}+BN)=\Theta(N^{3/2})$.
  • Shellsort is superior to straight insertion in this case because its empirically observed growth rate is $N^{3/2}$ versus $N^2$ for straight insertion.