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 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.
- Publisher copy:
- Pubs id:
- Local pid:
- Deposit date:
- Copyright date:
If you are the owner of this record, you can report an update to it here: Report update to this record