2026-07-22T13:39:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1289 2024-03-06T11:07:42Z ddc:004 open_access

Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise Manthey, Bodo Tantau, Till Smoothed Analysis Binary Search Trees Quicksort Left-to-right Maxima 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bodo Manthey and Till Tantau 2007 Is Part Of Dagstuhl Seminar Proceedings, Volume 7391, Probabilistic Methods in the Design and Analysis of Algorithms (2007) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.07391.3 urn:nbn:de:0030-drops-12893 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07391.3 eng https://creativecommons.org/licenses/by/4.0/legalcode