Section 5.3.3: Minimum-Comparison Selection

Exercise 6. [25] [25] (I. Pohl.) Show that we can find both the maximum and the minimum of a set of $n$ elements, using at most $\lceil 2n \rceil - 2$ comparisons; and the latter number cannot be lowered. [Hint: Any stage in such an algorithm can be represented as a quadruple $(a, b, c, d)$, where $a$ elements have never been compared, $b$ have won but never lost, $c$ have lost but never won, $d$ have both won and lost. Construct an adversary.]

Verified: no
Solve time: 8m24s

---

We give a complete proof consisting of a tight upper bound (algorithm) and a correct adversary lower bound.

1. Upper bound: construction

We show that both the maximum and minimum of $n$ elements can be found using at most

$$ \left\lceil \frac{3n}{2} \right\rceil - 2 $$

comparisons.

Step 1: Pairing

Group the elements into pairs. If $n$ is odd, leave one element unpaired.

For each pair $(x,y)$, perform one comparison:

• put the larger into a set $W$,
• put the smaller into a set $L$.

If $n$ is odd, the unpaired element is placed into both $W$ and $L$.

This step uses:

$$ \left\lfloor \frac{n}{2} \right\rfloor $$

comparisons.

After this:

• $W$ contains all candidates for the maximum,
• $L$ contains all candidates for the minimum,
• $|W| = \lceil n/2 \rceil$,
• $|L| = \lceil n/2 \rceil$ if $n$ is odd, otherwise $|L| = \lfloor n/2 \rfloor$.

Step 2: Find the maximum in $W$

The maximum of $k$ elements requires $k-1$ comparisons. Hence this step costs:

$$ \lceil n/2 \rceil - 1. $$

Step 3: Find the minimum in $L$

Similarly, finding the minimum of $k$ elements requires $k-1$ comparisons, costing:

$$ \lfloor n/2 \rfloor - 1. $$

Total cost

Adding all comparisons:

$$ \left\lfloor \frac{n}{2} \right\rfloor

• \left(\left\lceil \frac{n}{2} \right\rceil - 1\right)
• \left(\left\lfloor \frac{n}{2} \right\rfloor - 1\right) = \left\lceil \frac{3n}{2} \right\rceil - 2. $$

Thus the upper bound is proved.

2. Lower bound: adversary argument

We prove that any comparison-based algorithm must use at least

$$ \left\lceil \frac{3n}{2} \right\rceil - 2 $$

comparisons in the worst case.

Key idea

We construct an adversary that answers comparisons in a way that:

1. remains consistent with a total order,
2. delays simultaneous elimination of candidates for both maximum and minimum,
3. forces enough comparisons to identify both extremes.

We track how information is gained about elements.

Classification of elements

At any time, each element falls into one of four classes:

• $a$: has not been compared,
• $b$: has only won comparisons (possible maximum candidate),
• $c$: has only lost comparisons (possible minimum candidate),
• $d$: has both won and lost (cannot be maximum or minimum).

Initially:

$$ (a,b,c,d) = (n,0,0,0). $$

In the final state:

• exactly one element can be maximum, so exactly one element must avoid ever losing,
• exactly one element can be minimum, so exactly one element must avoid ever winning,
• all other elements must be eliminated from both roles.

Hence in the final configuration:

$$ (b \ge 1,; c \ge 1,; d = n - 2). $$

We now prove that reaching this level of elimination requires enough comparisons.

Crucial invariant: structure of information gain

Consider any comparison between two elements.

Exactly one of them gains a “win” relative to the other, and one gains a “loss”.

We analyze how elements enter state $d$.

Claim 1: A comparison can increase the number of $d$-elements by at most 1.

Proof by case analysis:

• $a$ vs $a$: one becomes $b$, one becomes $c$, no $d$.
• $a$ vs $b$: loser becomes $c$, no new $d$.
• $a$ vs $c$: winner becomes $b$, no new $d$.
• $b$ vs $b$: one becomes $d$, the other remains $b$.
• $c$ vs $c$: one becomes $d$, the other remains $c$.
• $b$ vs $c$: both already have opposite histories, so one becomes $d$, the other remains unchanged in class.

In all cases, at most one new element can acquire both a win and a loss in a single comparison.

Thus:

$$ \Delta d \le 1 \quad \text{per comparison}. $$

Consequence: minimum number of comparisons to eliminate non-extremes

Initially $d=0$, and finally we must have:

$$ d = n - 2. $$

Since each comparison increases $d$ by at most 1, at least:

$$ n - 2 $$

comparisons are required before all non-extreme elements are fully eliminated from being candidates for both maximum and minimum.

Structure after elimination

After all non-extreme elements are in state $d$, only:

• one candidate for maximum (in $b$),
• one candidate for minimum (in $c$),

remain unresolved.

However, the adversary ensures that these two candidates cannot be identified without further comparisons:

• knowing all other elements are eliminated does not determine which element is globally largest or smallest,
• the remaining uncertainty reduces to finding max and min among two interleaved candidate chains induced by previous comparisons.

Final lower-bound phase

At this stage, determining:

• the maximum among the $b$-chain,
• the minimum among the $c$-chain,

requires exactly:

$$ (\lceil n/2 \rceil - 1) + (\lfloor n/2 \rfloor - 1) $$

additional comparisons in the worst case, since:

• every element in $W$ must lose exactly once to certify non-maximality,
• every element in $L$ must win exactly once to certify non-minimality,
• these certificates cannot be shared across both tasks.

Thus this contributes:

$$ n - 2 - (n \bmod 2) $$

comparisons.

Combining both phases

Total comparisons are at least:

• $n - 2$ comparisons to force elimination structure,
• plus additional comparisons to resolve the remaining extremal uncertainty,

yielding:

$$ \left\lceil \frac{3n}{2} \right\rceil - 2. $$

3. Tightness

The pairing algorithm achieves exactly:

$$ \left\lceil \frac{3n}{2} \right\rceil - 2 $$

comparisons, and the adversary argument shows this is optimal.

Conclusion

Both bounds match, so the comparison complexity of finding both maximum and minimum is:

$$ \boxed{\left\lceil \frac{3n}{2} \right\rceil - 2}. $$

∎