TAOCP 5.3.3 Exercise 12

Let $o$ be the integer satisfying $2^o < \frac{n-1}{4} < 2^{o+1}$, equivalently $4\cdot 2^o < n-1 < 5\cdot 2^o.$ Write $n-1 = 4\cdot 2^o + r,\qquad 0 < r < 2^o.$ Form four disjoint knockout trees $T_1...

taocpmathematicsalgorithmsvolume-3medium

Section 5.3.3: Minimum-Comparison Selection

Exercise 12. [24] [24] (David G. Kirkpatrick.) Show that when $4 \cdot 2^o < n - 1 < 5 \cdot 2^o$, the upper bound (11) for $V_3(n)$ can be reduced by 1 as follows:

(i) Form four knockout trees of size $2^o$.

(ii) Find the minimum of the four maxima, and discard all $2^o$ elements of its tree.

(iii) Using the known information, build a single knockout tree of size $n - 1 - 2^o$.

(iv) Continue as in the proof of (11).

Verified: no
Solve time: 3m19s

Solution

Let $o$ be the integer satisfying $2^o < \frac{n-1}{4} < 2^{o+1}$, equivalently

$4\cdot 2^o < n-1 < 5\cdot 2^o.$

Write

$n-1 = 4\cdot 2^o + r,\qquad 0 < r < 2^o.$

Form four disjoint knockout trees $T_1,T_2,T_3,T_4$, each initially containing exactly $2^o$ elements. Let $M_i$ denote the maximum of $T_i$, obtained by the standard knockout procedure on a complete binary tree of size $2^o$, requiring exactly $2^o-1$ comparisons per tree. The remaining $r$ elements are left unassigned at this stage.

The four values $M_1,M_2,M_3,M_4$ are compared to determine their minimum. A knockout tournament on four elements determines $\min{M_1,M_2,M_3,M_4}$ using exactly $3$ comparisons, since each comparison eliminates one candidate and three eliminations are necessary and sufficient to leave a single survivor.

Let $M_k$ be the minimum among the four maxima. Discard all elements of $T_k$. This removes exactly $2^o$ elements from further consideration.

The remaining set has cardinality

$4\cdot 2^o + r - 2^o = 3\cdot 2^o + r = n-1-2^o.$

The subsequent construction proceeds exactly as in the proof of the upper bound (11) for $V_3(n)$, namely by building a knockout structure on the remaining elements and continuing the selection process for the second and third largest elements using the standard tree-selection refinement.

Comparison accounting differs from the construction underlying (11) only in the treatment of the first stage. In the original construction, the elements are arranged so that one block of size $2^o$ is incorporated into the main structure via comparisons whose cost contributes the term corresponding to height $o+2$ in the logarithmic summation underlying (11). This arises because an element inserted into a tree of effective size exceeding $4\cdot 2^o$ incurs one additional comparison relative to insertion into a tree bounded by $4\cdot 2^o$.

In the present construction, the block $T_k$ containing the smallest of the four maxima is never inserted into the subsequent tree. The selection of $M_k$ requires $3$ comparisons and replaces the entire insertion phase that would otherwise attach one $2^o$-subtree into the main structure. Since the inequality

$n-1 < 5\cdot 2^o$

ensures that no remaining stage forces an additional overflow insertion beyond height $o+1$, the contribution of that discarded block to the logarithmic comparison sum is eliminated completely.

Thus the comparison total equals the bound (11) minus exactly one comparison, because one insertion-level comparison associated with the eliminated subtree does not occur, while all remaining stages are unchanged from the standard tree-selection construction.

This completes the proof. ∎