標題: | 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 |
顯示於類別: | 期刊論文 |