Asymptotic distributions for Random Median Quicksort
The first complete running time analysis of a stochastic divide and conquer algorithm was given for Quicksort, a sorting algorithm invented 1961 by Hoare. We analyse here the variant Random Median Quicksort. The analysis includes the expectation, the asymptotic distribution, the moments and exponential moments. The asymptotic distribution is characterized by a stochastic fixed point equation. The basic technic will be generating functions and the contraction method.
quicksort sorting algorithm stochastic fixed point equation contraction method analysis of algorithm recursive equation divide-and-conquer algorithm euler differential equation