the lower bound for finding max and min together
Finding the maximum alone costs n-1 comparisons; finding the minimum alone also costs n-1. The lazy way to get both is to run each scan separately for about 2n - 2 comparisons. But you can be cleverer, and the surprising answer is that finding the max AND the min together needs only about 3n/2 comparisons — exactly ceil(3n/2) - 2 in the worst case. This is a lovely example where a lower bound matches a non-obvious optimal algorithm, well below the naive 2n.
The clever algorithm processes elements in PAIRS. Take two new elements and compare them to each other (1 comparison); the smaller is a candidate for the min, the larger for the max. Then compare the smaller against the running min (1 comparison) and the larger against the running max (1 comparison). So each pair of elements costs just 3 comparisons and updates both extremes, versus 4 if you handled the two elements independently for each extreme. That gives roughly 3n/2 total. The matching lower bound uses an adversary that tracks, for each element, whether it has ever 'won' a comparison and whether it has ever 'lost'. To certify the max, every element except one must have lost at least once; to certify the min, every element except one must have won at least once. The adversary shows a single comparison can supply at most one new 'has-lost' label and at most one new 'has-won' label, and counts how many such labels are still missing, forcing about 3n/2 comparisons.
Two honest points. First, the exact bound ceil(3n/2) - 2 depends slightly on whether n is even or odd, because of how the leftover element is handled when pairing — the clean 3n/2 picture is the even case. Second, like all results here it is comparison-model and worst-case. The real lesson is conceptual: combining two computations can be cheaper than doing them separately, because work spent on one (the pairwise comparison) does double duty. Recognising that shared work is what beats the naive 2n bound, and the adversary argument certifies you cannot do better than 3n/2.
For n = 6 (three pairs): each pair costs 3 comparisons, giving 9 = 3n/2, well under the naive 2n-2 = 10. The exact worst-case formula ceil(3*6/2) - 2 = 7 applies when you seed the extremes from the first pair, saving a couple of comparisons at the start.
Compare elements in pairs so one comparison routes each toward min-side or max-side: ~3n/2 total.
The naive 2n-2 (find max, then find min) is NOT optimal; pairing beats it to ~3n/2. The exact constant ceil(3n/2)-2 shifts a little with the parity of n. It is a comparison-model, worst-case count.