×

On lower bounds for selecting the median. (English) Zbl 0977.68042

Summary: We present a reformulation of the \(2n+o(n)\) lower bound of S. W. Bent and J. W. John [Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 213-216 (1985)] 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\).

MSC:

68Q25 Analysis of algorithms and problem complexity
06A07 Combinatorics of partially ordered sets
68R05 Combinatorics in computer science
PDFBibTeX XMLCite
Full Text: DOI