A note on the quicksort asymptotics1. Issue 4 (19th November 2013) - Fuchs, Michael
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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7rz3w" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />1≤p<∞</alternatives>Copyright © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 677–687, 2015