Quicksort and Large Deviations.
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...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Journal article |
| Language: | English |
| Published: |
Springer
2012
|
| _version_ | 1826263624911421440 |
|---|---|
| author | McDiarmid, C |
| author2 | Kucera, A |
| author_facet | Kucera, A McDiarmid, C |
| author_sort | McDiarmid, C |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T19:54:45Z |
| format | Journal article |
| id | oxford-uuid:252e335b-84cc-4256-958f-491b86acf21e |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T19:54:45Z |
| publishDate | 2012 |
| publisher | Springer |
| record_format | dspace |
| spelling | oxford-uuid:252e335b-84cc-4256-958f-491b86acf21e2022-03-26T11:54:17ZQuicksort and Large Deviations.Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:252e335b-84cc-4256-958f-491b86acf21eEnglishSymplectic Elements at OxfordSpringer2012McDiarmid, CKucera, AHenzinger, TNesetril, JVojnar, TAntos, DQuicksort 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. |
| spellingShingle | McDiarmid, C Quicksort and Large Deviations. |
| title | Quicksort and Large Deviations. |
| title_full | Quicksort and Large Deviations. |
| title_fullStr | Quicksort and Large Deviations. |
| title_full_unstemmed | Quicksort and Large Deviations. |
| title_short | Quicksort and Large Deviations. |
| title_sort | quicksort and large deviations |
| work_keys_str_mv | AT mcdiarmidc quicksortandlargedeviations |