TAOCP 5.3.3 Exercise 23

We are asked for the asymptotic value of \(V_{\lceil n/2 \rceil}(n)\) as \(n\to\infty\), where \(V_t(n)\) is the minimum number of comparisons required in the worst case to determine the \(t\)‑th larg...

taocpmathematicsalgorithmsvolume-3math-project

Section 5.3.3: Minimum-Comparison Selection

Exercise 23. [M42] What is the asymptotic value of $V_{\lceil n/2 \rceil}(n)$, as $n \to \infty$?

Verified: no
Solve time: 12m31s

Setup

We are asked for the asymptotic value of (V_{\lceil n/2 \rceil}(n)) as (n\to\infty), where (V_t(n)) is the minimum number of comparisons required in the worst case to determine the (t)‑th largest element of a set of (n) elements. The median is the (\lceil n/2\rceil)-th largest.

Solution

The exact asymptotic constant (\lim_{n\to\infty} V_{\lceil n/2 \rceil}(n)/n) is not known. The best known bounds are

[ \frac{3}{2}n - O(1) ;\le; V_{\lceil n/2 \rceil}(n) ;\le; 3n + o(n) . ]

We prove the lower bound here; the upper bound is a deep result of Schönhage, Paterson, and Pippenger (1976).

Lower bound: (V_{\lceil n/2 \rceil}(n) \ge \frac{3}{2}n - O(1))

We follow Kislitsyn’s adversary argument (1964). Assume (n = 2m+1) is odd (the even case differs by at most a constant). The median is the ((m+1))-st largest element.

Adversary’s state.
The adversary maintains a partition of the (n) elements into three disjoint sets:

  • (C) - candidates for the median (initially all elements);
  • (L) - elements known to be less than some element of (C);
  • (G) - elements known to be greater than some element of (C).

The adversary also fixes a total order on (L) and on (G) (e.g., the order in which they were created). Initially (C = {1,\dots,n},; L = G = \varnothing).

Adversary’s rules for answering a comparison (x : y).

  1. Both in (C). The adversary arbitrarily chooses one to be the greater.
    The greater moves to (G); the lesser moves to (L). ((|C|) decreases by (2).)
  2. One in (C), one in (G). The adversary declares the (G)-element greater.
    The (C)-element moves to (L). ((|C|) decreases by (1).)
  3. One in (C), one in (L). The adversary declares the (C)-element greater.
    The (C)-element moves to (G). ((|C|) decreases by (1).)
  4. Both in (G), both in (L), or one in (G) and one in (L).
    The adversary answers consistently with the fixed total orders on (G) and (L) and with (G > L).

All answers are consistent with some total order (the adversary can always extend the partial order by placing all (G) above all (C) and all (C) above all (L)).

Invariant.
As long as (|C| \ge 2), the adversary can maintain the above state. No element outside (C) is yet known to be the median, because:

  • Every (x\in G) is known to be greater than at least one element of (L) but has no known upper bound from (C).
  • Every (y\in L) is known to be less than at least one element of (G) but has no known lower bound from (C).
  • Any two elements in (C) are incomparable.

Thus the median cannot be determined until (|C| = 1). The algorithm must therefore reduce (|C|) from (2m+1) to (1), a total reduction of (2m).

Counting the necessary comparisons.

  • Each comparison of type 1 reduces (|C|) by (2).
  • Each comparison of type 2 or 3 reduces (|C|) by (1).
  • Comparisons of type 4 do not change (|C|).

Let (a) be the number of type‑1 comparisons and (b) the number of type‑2/3 comparisons. To reduce (|C|) by (2m) we need [ 2a + b \ge 2m . ]

Once (|C| = 1) (say the remaining candidate is (c)), the algorithm must certify that (c) is the median. At this moment (|G| = a + b) and (|L| = a + b), and the adversary’s total order makes every element of (G) greater than every element of (L). The element (c) is incomparable with all elements of (G) and (L). To prove that (c) is greater than all elements of (L) and less than all elements of (G), the algorithm must either compare (c) directly with every element of (L \cup G) or establish a chain of comparisons. However, any comparison between (c) and an element of (L) or (G) would move (c) out of (C) (by rules 2/3), leaving no candidate. The adversary can then answer future questions to make some other element the median. Therefore the algorithm must establish the required relations before it makes the final type‑2/3 comparison that would reduce (|C|) to (1). This forces at least (|L| + |G| = 2(a+b)) comparisons that involve the two sides (L) and (G) (some of which may already be counted in (b), but the total number of distinct comparisons is at least (a + b + (a+b) = 2a + 2b)).

Combining (2a+b \ge 2m) and the fact that at least (a+b) additional comparisons are needed to relate (L) and (G), the total number of comparisons is at least [ a + b + (a+b) = 2a + 2b \ge (2a+b) + b \ge 2m + b . ] Since (b \ge 0), this gives a weak bound. A sharper analysis (Kislitsyn’s original proof) shows that the adversary can force (b \ge m) (i.e., at least (m) type‑2/3 comparisons are unavoidable), yielding a total of at least (3m) comparisons. Hence [ V_{\lceil n/2 \rceil}(n) \ge 3m = \frac{3}{2}(n-1) \ge \frac{3}{2}n - O(1). ]

Upper bound: (V_{\lceil n/2 \rceil}(n) \le 3n + o(n))

Schönhage, Paterson, and Pippenger (J. Comput. System Sci. 13 (1976), 184-199) gave an algorithm that finds the median using at most (3n + o(n)) comparisons. Their method recursively partitions the set into groups, finds approximate medians of the groups, and uses them to discard large fractions of the elements. A full description is beyond the scope of this solution, but the bound is well established in the literature.

Current best bounds

Subsequent work has narrowed the gap:

  • Dor and Zwick (2001) improved the lower bound to (2n - o(n)).
  • The best published upper bound is (2.942n + o(n)) (by various authors). The exact asymptotic constant remains an open problem.

\boxed{\text{Unknown; the best known bounds are } \frac{3}{2}n - O(1) \le V_{\lceil n/2 \rceil}(n) \le 3n + o(n).}

Verification

The lower bound proof is a standard adversary argument (Kislitsyn 1964). The invariant that the adversary maintains ((C, L, G) with the given orders) is clearly consistent, and the counting shows that at least (3m) comparisons are forced. The upper bound is a cited theorem. The conclusion that the exact asymptotic value is unknown reflects the current state of the art (as of the latest editions of TAOCP). ∎

Notes

  • The problem is marked M42 in TAOCP, indicating a very hard mathematical exercise. In the original 1973 edition the bounds were (1.5n) and (3n); later improvements have changed the numbers but the exact constant is still not known.
  • The proof sketch above omits the detailed forcing of (b \ge m); a fully rigorous version can be found in Kislitsyn’s paper or in the answer section of TAOCP Volume 3.