On a multivariate contraction method for random recursive structures with applications to quicksort
The contraction method for recursive algorithms is extended to the multivariate analysis of vectors of parameters of recursive structures and algorithms. We prove a general multivariate limit law, which also leads to an approach to asymptotic covariances and correlations of the parameters. As an application, the asymptotic correlations and a bivariate limit law for the number of key comparisons and exchanges of median-of-(2t + 1) Quick, sort are given. Moreover, for the Quicksort programs analyzed by Sedgewick the exact order of the standard deviation and a limit law follow, considering all the parameters counted by Sedgewick. (C) 2001 John Wiley & Sons, Inc.
contraction method quicksort multivariate limit law analysis of algorithms median-of-(2t+1)