Exact L^2-distance from the limit for QuickSort key comparisons (extended abstract)

Details Exact L^2-distance from the limit for QuickSort key comparisons (extended abstract) Exact L^2-distance from the limit for QuickSort key comparisons (extended abstract)

2012-01-31

arxiv.org/abs/1201.6445v1

Mathematics

Probability

Scientific paper

Using a recursive approach, we obtain a simple exact expression for the L^2-distance from the limit in R\'egnier'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}.

Affiliated with

Also associated with

No associations

Rating

Exact L^2-distance from the limit for QuickSort key comparisons (extended abstract) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Exact L^2-distance from the limit for QuickSort key comparisons (extended abstract), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exact L^2-distance from the limit for QuickSort key comparisons (extended abstract) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-56520