Journal article icon

Journal article

Quicksort and Large Deviations.

Abstract:
Quicksort may be the most familiar and important randomised algorithm studied in computer science. It is well known that the expected number of comparisons on any input of n distinct keys is Θ(n ln n), and the probability of a large deviation above the expected value is very small. This probability was well estimated some time ago, with an ad-hoc proof: we shall revisit this result in the light of further work on concentration. © 2013 Springer-Verlag.

Actions


Access Document


Publisher copy:
10.1007/978-3-642-36046-6_5

Authors


Contributors

Role:
Editor
Role:
Editor
Role:
Editor
Role:
Editor
Role:
Editor
Publisher:
Springer Publisher's website
Journal:
MEMICS
Volume:
7721
Pages:
43-52
Publication date:
2012-01-01
DOI:
EISSN:
1611-3349
ISSN:
0302-9743
URN:
uuid:252e335b-84cc-4256-958f-491b86acf21e
Source identifiers:
365269
Local pid:
pubs:365269
Language:
English

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP