Computational Complexity - Research Seminar
Nima Zeini: Smoothed Lower Bound for Quicksort using Median-of-Three under Additive Noise II
May 13, 2008, 10:30 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.