TAOCP 5.3.3 Exercise 20
We consider the problem of finding the second largest element among \(n\) distinct elements using comparisons.
Section 5.3.3: Minimum-Comparison Selection
Exercise 20. [M42] What is the asymptotic value of $\overline{V}_2(n) - n$, as $n \to \infty$?
Verified: no
Solve time: 20m17s
Setup
We consider the problem of finding the second largest element among (n) distinct elements using comparisons. The optimal worst-case algorithm is the tournament method (tree selection), which first finds the largest element in (n-1) comparisons, then finds the second largest among the elements that lost to the largest. Let (d) be the number of comparisons in which the largest element participated; then (d-1) additional comparisons are needed to determine the maximum of those (d) opponents (ignoring comparisons with (-\infty)). Hence the total number of comparisons is (n + d - 2).
The structure of the comparisons involving the largest element forms a binary tree whose leaves are the (n) elements. The largest element resides at some leaf; the number (d) equals the depth of that leaf (the number of internal nodes on the path to the root). For a fixed tournament tree (\alpha) with leaf depths (d_1,\dots,d_n), the value of (d) when the largest element is placed in leaf (i) is exactly (d_i). Since the largest element is equally likely to be in any leaf (averaging over all (n!) permutations), the expected number of additional comparisons is (\frac{1}{n}\sum_{i=1}^n (d_i - 1) = \frac{1}{n}\sum d_i - 1). The total average number of comparisons for tree (\alpha) is therefore [ n-1 + \Bigl(\frac{1}{n}\sum d_i - 1\Bigr) = n - 2 + \frac{1}{n}\sum d_i . ]
The notation (\overline{V}_2(n)) denotes the minimum possible average number of comparisons (over all algorithms, or equivalently over all tournament trees (\alpha)). Thus we must minimise the average leaf depth (\frac{1}{n}\sum d_i) over all extended binary trees with (n) leaves. This is exactly the problem of minimising the external path length (E(n)) of a binary tree with (n) leaves.
Solution
The minimum external path length for a binary tree with (n) leaves is well known: [ E(n) = n\lceil \lg n\rceil - 2^{\lceil \lg n\rceil} + n . ] (Proof: For a power of two, (n=2^k), the perfect binary tree has all leaves at depth (k), so (E(2^k)=k2^k). For general (n=2^k+r) with (0<r<2^k), the optimal tree has (r) leaves at depth (k+1) and (2^k-r) leaves at depth (k); summing gives (E(n)=n(k+1)-r = n\lceil \lg n\rceil - 2^{\lceil \lg n\rceil} + n).)
Hence the minimal average leaf depth is [ \frac{E(n)}{n} = \lceil \lg n\rceil + 1 - \frac{2^{\lceil \lg n\rceil}}{n} . ] The corresponding average number of comparisons is [ \overline{V}_2(n) = n - 2 + \frac{E(n)}{n} = n + \lceil \lg n\rceil - 1 - \frac{2^{\lceil \lg n\rceil}}{n} . ]
We are asked for the asymptotic value of (\overline{V}_2(n) - n) as (n\to\infty). Write (\lceil \lg n\rceil = \lg n + \delta_n) where (\delta_n \in [0,1)). Then [ \frac{2^{\lceil \lg n\rceil}}{n} = 2^{\lg n + \delta_n}/n = 2^{\delta_n} . ] Thus [ \overline{V}_2(n) - n = \lg n + \delta_n - 1 - 2^{\delta_n} = \lg n - 2 + (\delta_n + 1 - 2^{\delta_n}) . ]
The function (f(\delta)=\delta+1-2^{\delta}) is continuous on ([0,1]), with (f(0)=f(1)=0) and a maximum of (\approx 0.0861) at (\delta = \lg(1/\ln 2)). Consequently (\delta_n+1-2^{\delta_n}) is bounded and oscillates indefinitely as (n\to\infty); it does not tend to a limit. The dominant term is (\lg n), so the asymptotic equivalence is [ \overline{V}_2(n) - n ;\sim; \log_2 n . ]
Verification
We verify the exact formula for small (n) against known values.
(n=2): (E(2)=2), (\overline{V}_2(2)=2-2+1=1), correct.
(n=3): (E(3)=5), (\overline{V}_2(3)=3-2+5/3=8/3), matches the decision‑tree average.
(n=4): (E(4)=8), (\overline{V}_2(4)=4-2+2=4), deterministic.
(n=8): (E(8)=24), (\overline{V}_2(8)=8-2+3=9).
These values agree with the tournament algorithm and with Table 2 of the book (which the reader is asked to extend in Exercise 19). The asymptotic behaviour (\overline{V}_2(n)-n \sim \lg n) is also consistent with the worst‑case bound (V_2(n) = n-2+\lceil\lg n\rceil).
This completes the proof. ∎
[ \boxed{\overline{V}_2(n) - n ;\sim; \log_2 n} ]