標題: A note on the quicksort asymptotics
作者: Fuchs, Michael
應用數學系
Department of Applied Mathematics
關鍵字: Quicksort;key comparisons;central limit theorem;L-p-distance;moment-transfer approach
公開日期: 1-七月-2015
摘要: In a recent paper, Bindjeme and Fill obtained a surprisingly easy exact formula for the L-2-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-3-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 L-p-distance for all 1p<Copyright (c) 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46,677-687, 2015
URI: http://dx.doi.org/10.1002/rsa.20524
http://hdl.handle.net/11536/124773
ISSN: 1042-9832
DOI: 10.1002/rsa.20524
期刊: RANDOM STRUCTURES & ALGORITHMS
Volume: 46
起始頁: 677
結束頁: 687
顯示於類別:期刊論文