License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.07391.3
URN: urn:nbn:de:0030-drops-12893
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/1289/
Go to the corresponding Portal

Manthey, Bodo ; Tantau, Till

Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise

pdf-format:
07391.MantheyBodo.Paper.1289.pdf (0.3 MB)

Abstract

While the height of binary search trees is linear in the worst case, their
average height is logarithmic. We investigate what happens in between, i.e.,
when the randomness is limited, by analyzing the smoothed height of binary
search trees: Randomly perturb a given (adversarial) sequence and then take
the expected height of the binary search tree generated by the resulting
sequence.

As perturbation models, we consider partial permutations, where some
elements are randomly permuted, and additive noise, where random numbers
are added to the adversarial sequence. We prove tight bounds for the
smoothed height of binary search trees under these models. We also obtain
tight bounds for smoothed number of left-to-right maxima. Furthermore, we
exploit the results obtained to get bounds for the smoothed number of
comparisons that quicksort needs.

BibTeX - Entry

@InProceedings{manthey_et_al:DagSemProc.07391.3,
  author =	{Manthey, Bodo and Tantau, Till},
  title =	{{Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise}},
  booktitle =	{Probabilistic Methods in the Design and Analysis of Algorithms},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7391},
  editor =	{Martin Dietzfelbinger and Shang-Hua Teng and Eli Upfal and Berthold V\"{o}cking},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/1289},
  URN =		{urn:nbn:de:0030-drops-12893},
  doi =		{10.4230/DagSemProc.07391.3},
  annote =	{Keywords: Smoothed Analysis, Binary Search Trees, Quicksort, Left-to-right Maxima}
}

Keywords: Smoothed Analysis, Binary Search Trees, Quicksort, Left-to-right Maxima
Collection: 07391 - Probabilistic Methods in the Design and Analysis of Algorithms
Issue Date: 2007
Date of publication: 18.12.2007

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI