Computational Complexity - Research Seminar
Bodo Manthey: Smoothed Analysis of Selection: Why Finding the Maximum is Harder Than Finding the Median
Nov. 13, 2008, 10:15 a.m.
E 1 3, Room 415
Hoare's selection algorithm, which is closely related to quicksort, is an easy-to-implement and usually fast algorithm for finding the k-th smallest element of a sequence. Its expected number of comparison is quadratic in the worst case and linear on average.
We give a smoothed analysis of Hoare's selection algorithm to analyze what happens between these two extremes: An adversary specifies a sequence of n numbers in [0,1]. Then these numbers are perturbed by adding random numbers of the interval [0,d]. We show that, for d < 2, we need an expected number of Ω(n3/2) comparisons. For d ≥ 2, finding the maximum still requires Ω(n3/2) comparisons, while for finding the median, O(n log n) (for d = 2) and O(n) (for d > 2) comparisons suffice.