
























Using a recursive approach, we obtain a simple exact expression for the L^2-distance from the limit in Régnier's (1989) classical limit theorem for the number of key comparisons required by QuickSort. A previous study by Fill and Janson (2002) using a similar approach found that the d_2-distance is of order between n^{-1} log n and n^{-1/2}, and another by Neininger and Ruschendorf (2002) found that the Zolotarev zeta_3-distance is of exact order n^{-1} log n. Our expression reveals that the L^2-distance is asymptotically equivalent to (2 n^{-1} ln n)^{1/2}.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。