A note on the quicksort asymptotics

Michael Fuchs*

*Corresponding author for this work

Research output: Contribution to journalArticle

7 Scopus citations

Abstract

In a recent paper, Bindjeme and Fill obtained a surprisingly easy exact formula for the L2-distance of the (normalized) number of comparisons of Quicksort under the uniform model to its limit. Shortly afterwards, Neininger proved a central limit theorem for the error. As a consequence, he obtained the asymptotics of the L3-distance. In this short note, we use the moment transfer approach to re-prove Neininger's result. As a consequence, we obtain the asymptotics of the Lp-distance for all 1≤p<∞

Original languageEnglish
Pages (from-to)677-687
Number of pages11
JournalRandom Structures and Algorithms
Volume46
Issue number4
DOIs
StatePublished - 1 Jul 2015

Keywords

  • Central limit theorem
  • Key comparisons
  • L<inf>p</inf>-distance
  • Moment-transfer approach
  • Quicksort

Fingerprint Dive into the research topics of 'A note on the quicksort asymptotics'. Together they form a unique fingerprint.

  • Cite this