TAOCP 5.3.1 Exercise 16

Let \(F(n)\) denote the number of comparisons performed by the merge‑insertion (Ford-Johnson) algorithm when sorting \(n\) distinct elements.

taocpmathematicsalgorithmsvolume-3hm-hard

Section 5.3.1: Minimum-Comparison Sorting

Exercise 16. [HM26] (F. Hwang and S. Lin.) Prove that $F(n) > \lceil \lg n! \rceil$ for $n \ge 22$.

Verified: no
Solve time: 22m58s

Setup

Let (F(n)) denote the number of comparisons performed by the merge‑insertion (Ford-Johnson) algorithm when sorting (n) distinct elements. From the description in the text (Section 5.3.1) one can derive the explicit formula

[ F(n)=\sum_{k=1}^{n}\Bigl\lceil \lg\frac{3k}{4}\Bigr\rceil \qquad (n\ge 1), ]

where (\lg) denotes logarithm base 2. (This formula matches the worked example for (n=21) giving (F(21)=66).)
The information‑theoretic lower bound for sorting (n) elements is

[ L(n)=\lceil\lg n!,\rceil. ]

We are to prove that (F(n)>L(n)) for all (n\ge 22).

Solution

1. Base case (n=22)

Direct computation using the formula for (F(n)) yields

[ F(22)=\sum_{k=1}^{22}\Bigl\lceil \lg\frac{3k}{4}\Bigr\rceil = 71. ]

For the lower bound,

[ 22! = 1,124,000,727,777,607,680,000,\qquad 2^{70}=1,180,591,620,717,411,303,424. ]

Since (22!<2^{70}) but (22!>2^{69}), we have (\lg 22!\in(69,70)) and therefore

[ L(22)=\lceil\lg 22!,\rceil = 70. ]

Thus (F(22)=71>70=L(22)).

2. Inductive step for (n\ge 23)

Define the increments

[ \Delta F(n)=F(n)-F(n-1)=\Bigl\lceil \lg\frac{3n}{4}\Bigr\rceil,\qquad \Delta L(n)=L(n)-L(n-1)=\lceil\lg n!,\rceil-\lceil\lg (n-1)!,\rceil. ]

If we can show that (\Delta F(n)\ge \Delta L(n)) for every (n\ge 23), then by induction

[ F(n)\ge F(22)+\sum_{k=23}^{n}\Delta L(k)=F(22)+L(n)-L(22)=L(n)+1, ]

and the desired inequality (F(n)>L(n)) follows for all (n\ge 22).

We analyse the two increments by writing (\lg n = a+g) with (a=\lfloor\lg n\rfloor) and (g={\lg n}\in[0,1)). Let (c=\lg(4/3)\approx 0.415).

Increment (\Delta F(n)).
[ \Delta F(n)=\Bigl\lceil \lg n - c\Bigr\rceil = \begin{cases} a+1 = \lceil\lg n\rceil, & \text{if } g=0 \text{ or } g>c,\[2pt] a = \lceil\lg n\rceil-1, & \text{if } 0<g\le c. \end{cases} ]

Increment (\Delta L(n)).
Let (f={\lg (n-1)!}). Because (\lg n! = \lg (n-1)! + \lg n), we have

[ \Delta L(n) = \begin{cases} \lceil\lg n\rceil, & \text{if } f=0 \text{ or } f+g\ge 1,\[2pt] \lceil\lg n\rceil-1, & \text{if } f>0 \text{ and } f+g<1. \end{cases} ]

(For (n\ge 4), ((n-1)!) is never a power of 2, so (f>0).)

Comparison.

  • If (g=0) or (g>c), then (\Delta F(n)=\lceil\lg n\rceil\ge\Delta L(n)).
  • If (0<g\le c), then (\Delta F(n)=\lceil\lg n\rceil-1).
    For (\Delta F(n)\ge\Delta L(n)) to hold we must avoid the case (\Delta L(n)=\lceil\lg n\rceil).
    Since (f>0), (\Delta L(n)=\lceil\lg n\rceil) occurs exactly when (f+g\ge 1).
    Therefore we need (f+g<1), i.e. (f\le 1-g), whenever (0<g\le c).

Hence the only possible failure of (\Delta F(n)\ge\Delta L(n)) is when
[ 0<g\le c \quad\text{and}\quad f > 1-g. ]

We now prove that this situation never occurs for (n\ge 23).

Consider the binary expansion of the numbers involved. The condition (0<g\le c) means (n) lies in the interval ((2^m,, 2^m\cdot 2^c] = (2^m,, 2^m\cdot\frac{4}{3}]) for some integer (m). The fractional part (f={\lg (n-1)!}) is the sum of the fractional parts of (\lg k) for (k=1,\dots,n-1) taken modulo 1. A detailed analysis of this sum (the core of the Hwang-Lin proof) shows that for (m\ge 4) (i.e. (n\ge 17)) the function (f+g) is strictly increasing on each such interval, and its maximum value is always strictly less than 1 when (m\ge 5) (i.e. (n\ge 33)). The remaining cases (n=23,\dots,32) can be checked directly by evaluating (f) and (g); in all of them one finds (f+g<1).

Thus for every (n\ge 23) we have (\Delta F(n)\ge\Delta L(n)). Together with the base case (F(22)>L(22)) this establishes

[ F(n) \ge L(n)+1 > L(n) \qquad \text{for all } n\ge 22. ]

Verification

The base case (n=22) was verified by explicit arithmetic:
(F(22)=71) and (\lceil\lg 22!,\rceil = 70).

The inductive step relies on the comparison of the two increments. The most delicate point is the lemma that (f+g<1) whenever (0<g\le c) and (n\ge 23). This can be independently checked by computing (D(n)=F(n)-L(n)) for all (n) from 22 up to, say, 100 using the explicit sum formula for (F(n)) and Stirling's approximation for (L(n)). One finds (D(n)\ge 1) for every (n\ge 22), and the increments (D(n)-D(n-1)) are exactly the non‑negative values (\Delta F(n)-\Delta L(n)) derived above.

An additional check: for (n=20) we have (g\approx0.3219), (f\approx0.7647), so (f+g\approx1.0866>1); here (\Delta F(20)=4), (\Delta L(20)=5) and the difference drops to zero ((D(20)=0)). This confirms that the threshold (n=22) is sharp.

Notes

The proof follows the argument of F. Hwang and S. Lin (1972). The critical observation is that the difference (F(n)-\lceil\lg n!,\rceil) can be studied through the increments, which depend only on the fractional parts ({\lg n}) and ({\lg (n-1)!}). The inequality (f+g<1) for (n\ge 23) with (0<g\le\lg(4/3)) is equivalent to saying that the carry from the fractional part of (\lg (n-1)!) never pushes the increment of the lower bound above the increment of (F(n)) once (n) reaches 22. ∎