Improved randomized selection

Simple item page
dc.creatorKiwiel, Krzysztof C.
dc.date2004-02-02
dc.date.accessioned2026-07-07T03:20:51Z
dc.date.available2026-07-07T03:20:51Z
dc.descriptionWe show that several versions of Floyd and Rivest's improved algorithm Select for finding the $k$th smallest of $n$ elements require at most $n+\min\{k,n-k\}+O(n^{1/2}\ln^{1/2}n)$ comparisons on average and with high probability. This rectifies the analysis of Floyd and Rivest, and extends it to the case of nondistinct elements. Encouraging computational results on large median-finding problems are reported.
dc.description14 pages
dc.identifierhttps://arxiv.org/abs/cs/0402005
dc.identifierhttp://arxiv.org/abs/cs/0402005
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31981
dc.subjectData Structures and Algorithms
dc.subjectF.2.2, G3
dc.titleImproved randomized selection
dc.typetext

Files

Collections

arXiv