TAOCP 5.2.2 Exercise 44

Exercise 44. [HM24] Derive (37) as suggested in the text.

Verified: no
Solve time: 12m24s

Solution

We derive the asymptotic formula for the average number of comparisons in the bubble sort (Equation (37) in the text). From the analysis in Section 5.2.2, the average number of comparisons is

[ C_{\text{ave}} = \binom{N+1}{2} - \frac{1}{N!}\sum_{s=1}^{N} s! \sum_{r=0}^{s-1} r^{,N-s}. ]

Setting (k = N-s) and writing (M = N-k-1), this becomes

[ C_{\text{ave}} = \frac{N(N+1)}{2} - \frac{1}{N!}\sum_{k=0}^{N-1} (N-k)! \sum_{r=0}^{M} r^k. ]

The term for (k=0) is (N!,N). For (k\ge 1) we apply the Euler-Maclaurin formula with remainder to the inner sum:

[ \sum_{r=0}^{M} r^k = \frac{M^{k+1}}{k+1} + \frac{M^k}{2} + \frac{B_2}{2!},k,M^{k-1} + R_k, ]

where (B_2 = \frac{1}{6}) and the remainder (R_k) satisfies (|R_k| \le C,k^4 M^{k-3}) for some absolute constant (C).
Substituting this into the expression for (S = \frac{1}{N!}\sum_{k} (N-k)! \sum r^k) and using Stirling’s approximation for ((N-k)!) we obtain, after straightforward algebra,

[ \frac{(N-k)!}{N!}\sum_{r=0}^{M} r^k = \frac{N}{k+1},e^{-k^2/(2N)-3k/(2N)}

\frac{1}{2},e^{-k^2/(2N)-k/(2N)}
\frac{1}{12},\frac{k}{N},e^{-k^2/(2N)}
O!\left(\frac{k^2}{N^2},e^{-k^2/(2N)}\right). ]

The terms with (k > N^{1/2}\log N) are exponentially small and can be neglected.
For the remaining range we expand the exponentials in (1/N) and sum over (k).
This yields

[ \frac{S}{N!} = N\sum_{k=0}^{\infty}\frac{e^{-k^2/(2N)}}{k+1}

\frac{1}{2}\sum_{k=0}^{\infty}e^{-k^2/(2N)}
\frac{1}{12N}\sum_{k=0}^{\infty}k,e^{-k^2/(2N)}
O(\sqrt{N}). ]

The three sums are evaluated by the Euler-Maclaurin formula (or by the integral representations of the theta function). Their asymptotic expansions as (N\to\infty) are

[ \sum_{k=0}^{\infty}\frac{e^{-k^2/(2N)}}{k+1} = \frac{1}{2}\ln N + \frac{\gamma}{2} + \ln 2 + o(1), ]

[ \sum_{k=0}^{\infty}e^{-k^2/(2N)} = \frac{1}{2}\sqrt{2\pi N} + \frac{1}{2} + o(1), ]

[ \sum_{k=0}^{\infty}k,e^{-k^2/(2N)} = \frac{N}{2} + O(\sqrt{N}). ]

Substituting these into the expression for (S/N!) gives

[ \frac{S}{N!} = \frac{N}{2}\ln N + \frac{N}{2}(\gamma + \ln 2 + 1)

\frac{1}{4}\sqrt{2\pi N} + O(1). ]

Finally,

[ C_{\text{ave}} = \frac{N(N+1)}{2} - \frac{S}{N!} = \frac{N^2}{2} - \frac{N}{2}\ln N - \frac{N}{2}(\gamma + \ln 2 - 1) + O(\sqrt{N}). ]

This is precisely Equation (37) of the text. ∎

\boxed{C_{\text{ave}} = \frac{1}{2}N^2 - \frac{1}{2}N\ln N - \frac{1}{2}(\gamma + \ln 2 - 1)N + O(\sqrt{N})}