# 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 Ω(*n*^{3/2}) comparisons. For *d* ≥ 2, finding the maximum still requires Ω(n^{3/2}) comparisons, while for finding the median, O(*n* log *n*) (for *d* = 2) and O(*n*) (for *d* > 2) comparisons suffice.