Variance of the number of Comparisons of Randomized Quicksort

Details Variance of the number of Comparisons of Randomized Quicksort Variance of the number of Comparisons of Randomized Quicksort

2010-06-21

arxiv.org/abs/1006.4063v1

Mathematics

Probability

20 pages. We do not intend to submit this elsewhere

Scientific paper

This paper gives a straightforward self-contained proof of the formula for the variance of the number of comparisons used by the Quicksort sorting algorithm when pivots are chosen uniformly at random. The result has been known for some time but we had not found a single source giving all details of the argument in a self-contained and explicit way. We hope these details may be of interest to students and others wishing to understand this calculation. No originality is claimed for the result.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-601314