Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




Computational Complexity - Research Seminar

Nima Zeini: Smoothed Lower Bound for Quicksort using Median-of-Three under Additive Noise I

May 6, 2008, 10:15 a.m.
E 1 3, Room 415

Quicksort is frequently employed in practice using the Median-of-3 pivot rule. In 2007, Manthey and Tantau performed a Smoothed Analysis of Quicksort using standard pivoting. We give an introduction to their approach and extend it to Median-of-3, yielding a lower bound for the smoothed running time.