A note on the quicksort asymptotics

Michael Fuchs

doi:10.1002/rsa.20524

A note on the quicksort asymptotics

Michael Fuchs^*

^*Corresponding author for this work

Department of Applied Mathematics

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

Abstract

In a recent paper, Bindjeme and Fill obtained a surprisingly easy exact formula for the L₂-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 L₃-distance. In this short note, we use the moment transfer approach to re-prove Neininger's result.

Original language	English
Pages (from-to)	677-687
Number of pages	11
Journal	Random Structures and Algorithms
Volume	46
Issue number	4
DOIs	https://doi.org/10.1002/rsa.20524
State	Published - 1 Jul 2015

Keywords

Central limit theorem
Key comparisons
L-distance
Moment-transfer approach
Quicksort

Access to Document

10.1002/rsa.20524

Cite this

@article{e9d96565ce4b470a8b02494d53580845,

title = "A note on the quicksort asymptotics",

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.",

keywords = "Central limit theorem, Key comparisons, L-distance, Moment-transfer approach, Quicksort",

author = "Michael Fuchs",

note = "Publisher Copyright: {\textcopyright} 2013 Wiley Periodicals, Inc.",

year = "2015",

month = jul,

day = "1",

doi = "10.1002/rsa.20524",

language = "English",

volume = "46",

pages = "677--687",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

number = "4",

}

TY - JOUR

T1 - A note on the quicksort asymptotics

AU - Fuchs, Michael

PY - 2015/7/1

Y1 - 2015/7/1

N2 - 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.

AB - 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.

KW - Central limit theorem

KW - Key comparisons

KW - L-distance

KW - Moment-transfer approach

KW - Quicksort

UR - http://www.scopus.com/inward/record.url?scp=84929278714&partnerID=8YFLogxK

U2 - 10.1002/rsa.20524

DO - 10.1002/rsa.20524

M3 - Article

AN - SCOPUS:84929278714

SN - 1042-9832

VL - 46

SP - 677

EP - 687

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 4

ER -

A note on the quicksort asymptotics

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this