On Lower Bounds for Selecting the Median

DOI10.1137/S0895480196309481zbMath0977.68042WikidataQ56959022 ScholiaQ56959022MaRDI QIDQ2719173

Uri Zwick, Staffan Ulfberg, Johan T. Håstad, Dorit Dor

Publication date: 21 June 2001

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

lower boundsmedian selectioncomparison algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Combinatorics of partially ordered sets (06A07)

Related Items (7)

Select with Groups of 3 or 4 ⋮ Unnamed Item ⋮ On partial sorting in restricted rounds ⋮ Finding a mediocre player ⋮ A selectable sloppy heap ⋮ Selection Algorithms with Small Groups ⋮ On Floyd and Rivest's SELECT algorithm

This page was built for publication: On Lower Bounds for Selecting the Median