TAOCP 5.2 Exercise 5
The changes preserve correctness.
Exercise 5. [**] [22] Does the following set of changes improve Program C?
New line 08a: INCX 0,2
Change line 10: JGE 5F
Change line 14: DECX 1
Delete line 15.
Verified: no
Solve time: 7m43s
The changes preserve correctness. After line 08a, register X contains
$\text{COUNT}[i]+j,$
because index register 2 contains $j$. When $K_i<K_j$, the original program increments $\text{COUNT}[j]$ and leaves $\text{COUNT}[i]$ unchanged. The modified program executes line 14, DECX 1, so X changes from $\text{COUNT}[i]+j$ to $\text{COUNT}[i]+(j-1)$, exactly compensating for the subsequent decrement of $j$ in line 16. When $K_i\ge K_j$, control goes directly to line 5F; the deletion of line 15 is offset by the fact that after line 16 the value of $j$ decreases by $1$, hence X again becomes $\text{COUNT}[i]+(j-1)$. Therefore the invariant
$X=\text{COUNT}[i]+j$
is maintained throughout the loop, and when $j=0$ we have $X=\text{COUNT}[i]$, so line 18 stores the correct value.
The running time is improved. New line 08a costs $1$ unit for every pair $(i,j)$, hence it adds $A$ units. Deleting line 15 removes $A-B$ executions, since line 15 was executed exactly when $K_i\ge K_j$. Line 14 changes from a jump costing $1$ unit, executed $B$ times, to DECX 1 costing $1$ unit, also executed $B$ times; hence this part is unchanged. The net change in running time is therefore
$A-(A-B)=B.$
The modified program requires
=13N+6A+4B-4$$ units. Since $B\ge0$, it is never slower and is faster whenever at least one inversion is present. Thus the modification is an improvement. The new running time is $$\boxed{13N+6A+4B-4}.$$