Phase change of limit laws in the quicksort recurrence under varying toll functions
We characterize all limit laws of the quicksort-type random variables defined recursively by L (X(n)) = L (XI(n) + X(n-1-I-n)* + T(n)) when the toll function T(n) varies and satisfies general conditions, where (X(n)), (X(n)*), (I(n), T(n)) are independent, I(n) is uniformly distributed over {0,..., n-1}, and L (X(n)) = L (X(n)*). When the toll function T(n) (cost needed to partition the original problem into smaller subproblems) is small (roughly lim sup(n-->infinity) log E (T(n)) / log n less than or equal to 1/2), X(n) is asymptotically normally distributed; nonnormal limit laws emerge when T(n) becomes larger. We give many new examples ranging from the number of exchanges in quicksort to sorting on a broadcast communication model, from an in-situ permutation algorithm to tree traversal algorithms, etc.
quicksort binary search trees analysis of algorithms limit distribution method of moments contraction method