the comparison lower bound for the median
The median-of-medians algorithm finds the median (or any k-th smallest) in O(n) comparisons in the worst case — surprisingly, you do NOT have to sort, which would cost n log n. A fair question is how few comparisons the median really needs. The lower bound says median selection requires at least a linear number of comparisons, Omega(n) — in fact strictly MORE than the n-1 needed just for the max. Finding the middle is provably harder than finding an extreme, though both are linear.
The easy half of the bound is a clean adversary observation: to report the median correctly, the algorithm must in particular have 'seen' every element — any element it never compared could secretly be anything, including a value that changes which element is the median. So at least n-1 comparisons are required just to involve everyone, the same floor as the max. The interesting half is that the median needs strictly more than that. An adversary argument shows the algorithm must, along the way, effectively prove that about n/2 elements are below the median and n/2 are above, and certifying both sides forces extra comparisons beyond merely touching each element. The best known lower bounds for the exact median are around 2n comparisons, and the best algorithms use a constant times n; pinning down the exact constant is a famous, still-open fine-grained question.
The honest takeaways. First, Omega(n) is tight in ORDER: linear-time selection (median of medians) achieves O(n), so the problem is Theta(n) comparisons — you never need to pay the n log n of full sorting just to find one order statistic. Second, the exact constant factor is genuinely subtle and not fully resolved, a reminder that 'we know it's linear' is not the same as 'we know it exactly'. Third, this is a comparison-model statement; the practical median-of-medians is linear but carries a larger hidden constant than quickselect, whose expected time is O(n) but whose worst case is O(n^2).
To certify that x is the median of n elements, you must show n/2 elements are <= x and n/2 are >= x. Any element never compared to anything could be an unseen value that displaces x, so all n must be touched — at least n-1 comparisons — and certifying both halves pushes the count strictly higher, toward ~2n in the best known bounds.
Every element must be involved, and both sides of the median must be certified — strictly more than the max needs.
Omega(n) is tight in order (selection is Theta(n)), so you never need n log n to find one order statistic. But the exact best constant for median comparisons is still not fully known — 'linear' is settled, the precise factor is not.