TAOCP 5.2.1 Exercise 4

Section 5.2.1: Sorting by Insertion

Exercise 4. [**] [M20] Find the minimum and maximum running times for Program S, as a function of N.

Verified: yes
Solve time: 16m17s

The running time of Program S is

$9B+10N-3A-9.$

By the results stated in Section 5.2.1,

$0\le A\le N-1,\qquad 0\le B\le \frac{N(N-1)}2.$

The minimum running time occurs when the file is already in order. Then there are no inversions, so $B=0$; there are no new left-to-right minima after the first key, so $A=0$. Hence

$9B+10N-3A-9=10N-9.$

Therefore the minimum running time is

$\boxed{10N-9}.$

The maximum running time occurs when the keys are in reverse order. Then every pair is an inversion, so

$B=\frac{N(N-1)}2,$

and every key after the first is a new left-to-right minimum, so

$A=N-1.$

Substituting into the running-time formula gives

=\frac{9N^2+5N-12}{2}.$$ Therefore the maximum running time is $$\boxed{\frac{9N^2+5N-12}{2}}.$$