A Detailed Analysis of Quicksort Running Time

by Shalosh B. Ekhad and Doron Zeilberger

.pdf   .ps   .tex

First Written: March 8, 2019

One of the greatest algorithms of all time is Quicksort, (it is ranked 7th in this top 10 list). Its average running time is famously O(n log(n)), and its variance, less famously, is O(n2) (hence its standard deviation is O(n)). But what about higher moments? Here we find explicit expressions for the first eight moments, their scaled limits, and we describe how to compute, approximately (but very accurately), percentiles of running time for any list-length.

Added March 12, 2019: Helmut Prodinger pointed our attention to this human-generated gem.

Added March 22, 2019: Sumit Kumar Jha pointed our attention to yet another human-generated gem.

# Sample Input and Output for QuickSortAnalsis.txt

• If you want to see the first 130 terms in the sequence of probablity generating functions of the random variable "Number of comparisons in Quicksort with lists of length n"

the input file generates the output file.

• If you want to see the the probablity generating function of the random variable "Number of comparisons in Quicksort with lists of length 150, in floating point

the input file generates the output file.

• If you want to see explicit expressionf or the first eight moments of the random variable "Number of comparisons in Quicksort with lists of length n" as a function of n, as well as their asympotic expressions and scaled limits

the input file generates the output file.

• If you want to see a computer-generated article about the above

the input file generates the output file.

• If you want to see a the approximate percentiles for the running time of Quicksort with a list with 10000 items

the input file generates the output file.

• If you want to see a the results of simulating quicksort on 10000 randomly chosen sequences of length 200, and also the theoretical values of the expectation, variance, skewness, and kurtosis,

the input file generates the output file.

• If you want to see a the results of simulating quicksort on 50000 randomly chosen sequences of length 200, and also the theoretical values of the expectation, variance, skewness, and kurtosis,

the input file generates the output file.

# Pictures

Articles of Doron Zeilberger