Smoothed analysis of binary search trees and quicksort under additive noise

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 se-quence 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 Θ ( nd+1 n/d+ n log n)