Modular smoothed analysis of median-of-three Quicksort
Loading...
Files
Submitted Version
Date
2014
Authors
Hennessy, Aoife
Schellekens, Michel P.
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
Published Version
Abstract
Spielman’s smoothed complexity - a hybrid between worst and average case complexity measures - relies on perturbations of input instances to determine where average-case behavior turns to worst-case. This approach simplifies the smoothed analysis and achieves greater precession in the expression of the smoothed complexity, where a recurrence equation is obtained as opposed to bounds. Moreover, the approach addresses, in this context, the formation of input instances–an open problem in smoothed complexity. In [23], we proposed a method supporting modular smoothed analysis and illustrated the method by determining the modular smoothed complexity of Quicksort. Here, we use the modular approach to calculate the median of three variant and compare these results with those in [23].
Description
Keywords
Modular smoothed analysis , MOQA , Median-of-three Quicksort
Citation
HENNESSY, A. & SCHELLEKENS, M. P. 2014. Modular smoothed analysis of median-of-three Quicksort. Submitted to: Discrete Mathematics. [Preprint]