Change search
ReferencesLink to record
Permanent link

Direct link
On lower bounds for selecting the median
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.ORCID iD: 0000-0002-5379-345X
2001 (English)In: SIAM Journal on Discrete Mathematics, ISSN 0895-4801, E-ISSN 1095-7146, Vol. 14, no 3, 299-311 p.Article in journal (Refereed) Published
Abstract [en]

We present a reformulation of the 2n + o(n) lower bound of Bent and John [Proceedings of the 17th Annual A CM 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 [n/2] disjoint pairs of elements must perform, in the worst case, at least 2.01n + o(n) comparisons. This provides strong evidence that selecting the median requires at least cn + o(n) comparisons for some c > 2.

Place, publisher, year, edition, pages
2001. Vol. 14, no 3, 299-311 p.
Keyword [en]
median selection, comparison algorithms, lower bounds
URN: urn:nbn:se:kth:diva-20987ISI: 000171372500004OAI: diva2:339684
QC 20100525Available from: 2010-08-10 Created: 2010-08-10Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Håstad, Johan
By organisation
Numerical Analysis and Computer Science, NADA
In the same journal
SIAM Journal on Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 22 hits
ReferencesLink to record
Permanent link

Direct link