A Detailed Analysis of Quicksort Running Time
classification
🧮 math.PR
math.CO
keywords
timerunningfamouslymomentsquicksortaccuratelyalgorithmsanalysis
read the original abstract
One of the greatest algorithms of all time is Quicksort. Its average running time is famously O(nlog(n)), and its variance, less famously, is O(n^2) (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
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.