Variance of the number of Comparisons of Randomized Quicksort
From MaRDI portal
Abstract: 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.
This page was built for publication: Variance of the number of Comparisons of Randomized Quicksort
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6219376)
