Smoothed analysis of left-to-right maxima with applications
Valentina Damerow, Bodo Manthey, Friedhelm Meyer auf der Heide, Harald Räcke, Christian Scheideler, Christian Sohler, Till Tantau · ACM Transactions on Algorithms · 2012
A left-to-right maximum in a sequence of n numbers s 1 , …, s n is a number that is strictly larger than all preceding numbers. In this article we present a smoothed analysis of the number of left-to-right maxima in the presence of additive random noise. We show that for every sequence of n numbers s i ∈ [0,1] that are perturbed by uniform noise from the interval [-ϵ,ϵ], the expected number of left-to-right maxima is Θ(√ n /ϵ + log n ) for ϵ>1/ n . For Gaussian noise with standard deviation σ we obtain a bound of O ((log 3/2 n )/σ + log n ). We apply our results to the analysis of the smoothed height of binary search trees and the smoothed number of comparisons in the quicksort algorithm and prove bounds of Θ(√ n /ϵ + log n ) and Θ( n /ϵ+1√ n /ϵ + n log n ), respectively, for uniform random noise from the interval [-ϵ,ϵ]. Our results can also be applied to bound the smoothed number of points on a convex hull of points in the two-dimensional plane and to smoothed motion complexity, a concept we describe in this article. We bound how often one needs to update a data structure storing the smallest axis-aligned box enclosing a set of points moving in d -dimensional space.