DMTCS Proceedings, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)

Font Size:  Small  Medium  Large

Exact L2-Distance from the Limit for QuickSort Key Comparisons (Extended Abstract)

Patrick Bindjeme, James Allen Fill

Abstract


Using a recursive approach, we obtain a simple exact expression for the L2-distance from the limit in the classical limit theorem of Régnier (1989) for the number of key comparisons required by QuickSort. A previous study by Fill and Janson (2002) using a similar approach found that the d2-distance is of order between n-1 logn and n-1/2, and another by Neininger and Ruschendorf (2002) found that the Zolotarev ζ3-distance is of exact order n-1 logn. Our expression reveals that the L2-distance is asymptotically equivalent to (2 n-1 lnn)1/2.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional