TAOCP 5.3.1 Exercise 15
The maximum number of comparisons for binary insertion is given in the text (Eq.
Section 5.3.1: Minimum-Comparison Sorting
Exercise 15. [M21] Determine the asymptotic behavior of $B(n)$ and $F(n)$ up to $O(\log n)$. [Hint: Show that in both cases the coefficient of $n$ involves the function shown in Fig. 37.]
Verified: no
Solve time: 13m12s
Solution
1. Binary insertion (B(n))
The maximum number of comparisons for binary insertion is given in the text (Eq. (3)) as
[ B(n) = \sum_{k=1}^{n}\lceil\lg k\rceil = n\lceil\lg n\rceil - 2^{\lceil\lg n\rceil} + 1 . ]
Let (x = \lg n) and write ({x}=x-\lfloor x\rfloor) for the fractional part.
For non‑integer (x) we have (\lceil x\rceil = x+1-{x}); for integer (x) we have (\lceil x\rceil = x) and ({x}=0). In both cases the difference is absorbed by the (O(\log n)) remainder, so we may write
[ \lceil\lg n\rceil = \lg n + 1 - {\lg n} + O(1/n) ]
and
[ 2^{\lceil\lg n\rceil} = 2^{\lg n+1-{\lg n}} = n\cdot 2^{1-{\lg n}} . ]
Substituting into the closed form yields
[ \begin{aligned} B(n) &= n\bigl(\lg n + 1 - {\lg n}\bigr) - n\cdot 2^{1-{\lg n}} + O(\log n) \ &= n\lg n + n\bigl(1 - {\lg n} - 2^{1-{\lg n}}\bigr) + O(\log n). \end{aligned} ]
Define the periodic function
[ f(t) = 1 - t - 2^{1-t}\qquad (0\le t<1), ]
which is precisely the function graphed in Fig. 37. Then
[ \boxed{B(n) = n\lg n + n,f({\lg n}) + O(\log n)} . ]
2. Merge insertion (F(n))
The Ford-Johnson merge‑insertion algorithm is analysed in the text. Its worst‑case comparison count (F(n)) satisfies the recurrence (Eq. (17))
[ F(n) = F(\lfloor n/2\rfloor) + \lfloor n/2\rfloor + \sum_{k=1}^{n-\lfloor n/2\rfloor} \left\lceil\lg\frac{2^{\lceil\lg k\rceil}+k}{2}\right\rceil . ]
Exercise 14 asks for a closed form of the sum; carrying out the same type of manipulation as for (B(n)) (or using the closed form provided in the answer to that exercise) one obtains
[ F(n) = n\lceil\lg n\rceil - 2^{\lceil\lg n\rceil} + 1 - \frac{n}{2} + O(\log n). ]
Replacing (\lceil\lg n\rceil) and (2^{\lceil\lg n\rceil}) by their expressions in terms of (\lg n) and ({\lg n}) as before gives
[ \begin{aligned} F(n) &= n\bigl(\lg n + 1 - {\lg n}\bigr) - n\cdot 2^{1-{\lg n}} + 1 - \frac{n}{2} + O(\log n) \ &= n\lg n + n\Bigl(\frac12 - {\lg n} - 2^{1-{\lg n}}\Bigr) + O(\log n) . \end{aligned} ]
Thus the coefficient of (n) is (f({\lg n})-\frac12), where (f) is again the function from Fig. 37. Hence
[ \boxed{F(n) = n\lg n + n\Bigl(\frac12 - {\lg n} - 2^{1-{\lg n}}\Bigr) + O(\log n)} . ]
Both asymptotic formulas have the shape (n\lg n + n\cdot g({\lg n}) + O(\log n)) where the periodic function (g) involves the function (f(t)=1-t-2^{1-t}) shown in Fig. 37. For binary insertion (g(t)=f(t)); for merge insertion (g(t)=f(t)-\frac12). This completes the derivation. ∎