Smoothed analysis of left-to-right maxima with applications

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 paper 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$ in $[0,1]$ that are perturbed by uniform noise from the interval $[-\epsilon,\epsilon]$, the expected number of left-to-right maxima is $\Theta(\sqrt{n/\epsilon} + \log n)$ for $\epsilon > 1/n.$ For Gaussian noise with standard deviation $\sigma$ we obtain a bound of $O((\log^{3/2} n)/ \sigma + \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 $\Theta(\sqrt{n/\epsilon} + \log n)$ and $\Theta(\frac{n}{\epsilon+1} \sqrt{n/\epsilon} + n \log n)$, respectively, for uniform random noise from the interval $[-\epsilon,\epsilon]$. 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 paper. 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.