TAOCP 5.2.1 Exercise 34

Section 5.2.1: Sorting by Insertion

Exercise 34. [M10] Verify formula (14).

Verified: no
Solve time: 22m

Formula (14) gives the running time of Program D (Shellsort) as
[ 9B + 10Nt - 3A - 10\sum_{s=0}^{t-1}h_s + 13t + 1 \quad \text{units}, ]
where (t) is the number of passes, (h_s) are the increments, (A) is the total number of times the index (i) decreases to zero, and (B) is the total number of moves.

The verification follows by multiplying each instruction’s frequency (shown in the program comments) by its execution time in the standard “unit” measure used throughout Section 5.2.1: 2 units for memory‑reference instructions (LDA, STA, LDX, STX, CMPA, LD4, ST1) and 1 unit for all others (ENT, ENN, INC, DEC, conditional jumps).

[ \begin{array}{c|c|c|c} \text{Line} & \text{Instruction} & \text{Frequency} & \text{Time} \ \hline 01 & \text{ENT3} & 1 & 1 \ 02 & \text{LD4} & t & 2t \ 03 & \text{ENT1} & t & t \ 04 & \text{ST1} & t & 2t \ 05 & \text{ST1} & t & 2t \ 06 & \text{ENN1} & t & t \ 07 & \text{ST1} & t & 2t \ 08 & \text{ENT1} & t & t \ 09 & \text{LDA} & Nt - S & 2(Nt - S) \ 10 & \text{ENT2} & Nt - S & Nt - S \ 11 & \text{CMPA} & B + Nt - S - A & 2(B + Nt - S - A) \ 12 & \text{JGE} & B + Nt - S - A & B + Nt - S - A \ 13 & \text{LDX} & B & 2B \ 14 & \text{STX} & B & 2B \ 15 & \text{DEC2} & B & B \ 16 & \text{J2P} & B & B \ 17 & \text{STA} & Nt - S & 2(Nt - S) \ 18 & \text{INC1} & Nt - S & Nt - S \ 19 & \text{J1NP} & Nt - S & Nt - S \ 20 & \text{DEC3} & t & t \ 21 & \text{J3NN} & t & t \ \hline \end{array} ]

Here (S = \sum_{s=0}^{t-1} h_s). Summing the contributions:

• (B): (2 + 1 + 2 + 2 + 1 + 1 = 9B)
• (Nt): (2 + 1 + 2 + 1 + 2 + 1 + 1 = 10Nt)
• (S): (-2 -1 -2 -1 -2 -1 -1 = -10S)
• (A): (-2 -1 = -3A)
• (t): (2+1+2+2+1+2+1+1+1 = 13t)
• Constant: (1)

Total (= 9B + 10Nt - 10S - 3A + 13t + 1), which matches formula (14). ∎

\boxed{9B + 10Nt - 3A - 10\sum_{s=0}^{t-1}h_s + 13t + 1}