Campus Event Calendar
Event Entry
What and Who
Smoothed Analysis of Selection: Why Finding the Maximum is Harder Than Finding the Median
Bodo Manthey
Fachrichtung Informatik - Saarbrücken
Talk
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 13 November 2008
10:15
60 Minutes
E1 3 - CS
014
Saarbrücken
Abstract
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 Omega(n^{3/2}) comparisons. For d>=2, finding the maximum still requires Omega(n^{3/2}) comparisons, while for finding the median, O(n log n) (for d = 2) and O(n) (for d > 2) comparisons suffice.
Contact
Bodo Manthey
5502
--email hidden
passcode not visible
logged in users only
gk-sek, 11/10/2008 13:06 -- Created document.