Approximating the limiting Quicksort distribution

Details Approximating the limiting Quicksort distribution Approximating the limiting Quicksort distribution

2001-05-29

arxiv.org/abs/math/0105246v1

Mathematics

Probability

30 pages. See also http://www.mts.jhu.edu/~fill/ and http://www.math.uu.se/~svante/ . Submitted for publication in January, 20

Scientific paper

The limiting distribution of the normalized number of comparisons used by Quicksort to sort an array of n numbers is known to be the unique fixed point with zero mean of a certain distributional transformation S. We study the convergence to the limiting distribution of the sequence of distributions obtained by iterating the transformation S, beginning with a (nearly) arbitrary starting distribution. We demonstrate geometrically fast convergence for various metrics and discuss some implications for numerical calculations of the limiting Quicksort distribution. Finally, we give companion lower bounds which show that the convergence is not faster than geometric.

Affiliated with

Also associated with

No associations

Rating

Approximating the limiting Quicksort distribution 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 Approximating the limiting Quicksort distribution, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximating the limiting Quicksort distribution will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-196770