On Lower Bounds for Selecting the Median
Dorit Dor, Johan Håstad, Staffan Ulfberg, Uri Zwick · SIAM Journal on Discrete Mathematics · 2001
We present a reformulation of the 2n+o(n) lower bound of Bent and John [Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985, pp. 213--216] for the number of comparisons needed for selecting the median of n elements. Our reformulation uses a weight function. Apart from giving a more intuitive proof for the lower bound, the new formulation opens up possibilities for improving it. We use the new formulation to show that any pair-forming median finding algorithm, i.e., a median finding algorithm that starts by comparing $\lfloor n/2\rfloor$ disjoint pairs of elements must perform, in the worst case, at least 2.01 n + o(n) comparisons. This provides strong evidence that selecting the median requires at least cn+o(n) comparisons for some c> 2.