Smoothed analysis of binary search trees and quicksort under additive noise

Bodo Manthey*, Till Tantau

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

Abstract

Binary search trees are a fundamental data structure and their height plays a key role in the analysis of divide-and-conquer algorithms like quicksort. We analyze their smoothed height under additive uniform noise: An adversary chooses a sequence of n real numbers in the range [0,1], each number is individually perturbed by adding a value drawn uniformly at random from an interval of size d, and the resulting numbers are inserted into a search tree. An analysis of the smoothed tree height subject to n and d lies at the heart of our paper: We prove that the smoothed height of binary search trees is (√ n/d + log n), where d ≥ 1/n may depend on n. Our analysis starts with the simpler problem of determining the smoothed number of left-to-right maxima in a sequence. We establish matching bounds, namely once more (√ n/d + log n). We also apply our findings to the performance of the quicksort algorithm and prove that the smoothed number of comparisons made by quicksort is (n/d+1 √ n/d + n log n).

Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2008
Subtitle of host publication33rd International Symposium, MFCS 2008, Toru'n, Poland, August 25-29, 2008. Proceedings
EditorsEdward Ochmański, Jerzy Tyszkiewicz
PublisherSpringer
Pages467-478
Number of pages12
ISBN (Electronic)978-3-540-85238-4
ISBN (Print)978-3-540-85237-7
DOIs
Publication statusPublished - 27 Oct 2008
Externally publishedYes
Event33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008: Mathematical Foundations of Computer Science - Torun, Poland, Torun, Poland
Duration: 25 Aug 200829 Aug 2008
Conference number: 33

Publication series

NameLecture Notes in Computer Science
Volume5162
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008
Abbreviated titleMFCS 2008
CountryPoland
CityTorun
Period25/08/0829/08/08
OtherAugust 27-31, 2008

Fingerprint Dive into the research topics of 'Smoothed analysis of binary search trees and quicksort under additive noise'. Together they form a unique fingerprint.

  • Cite this

    Manthey, B., & Tantau, T. (2008). Smoothed analysis of binary search trees and quicksort under additive noise. In E. Ochmański, & J. Tyszkiewicz (Eds.), Mathematical Foundations of Computer Science 2008 : 33rd International Symposium, MFCS 2008, Toru'n, Poland, August 25-29, 2008. Proceedings (pp. 467-478). (Lecture Notes in Computer Science; Vol. 5162). Springer. https://doi.org/10.1007/978-3-540-85238-4_38