Authors
Citation
L. Devroye, On the probablistic worst-case time of "Find", ALGORITHMIC, 31(3), 2001, pp. 291-303
Citations number
29
Categorie Soggetti
Engineering Mathematics
Journal title
ALGORITHMICA
ISSN journal
01784617
→ ACNP
Volume
31
Issue
3
Year of publication
2001
Pages
291 - 303
Database
ISI
SICI code
0178-4617(200111)31:3<291:OTPWTO>2.0.ZU;2-P
Abstract
We analyze the worst-case number of comparisons T-n of Hoare's selection al
gorithm FIND when the input is a random permutation, and worst case is meas
ured with respect to the rank k. We give a new short proof that T-n/n tends
to a limit distribution, and provide new bounds for the limiting distribut
ion.