On a multivariate contraction method for random recursive structures with applications to Quicksort
Ralph Neininger · Random Structures and Algorithms · 2001
Abstract 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‐(2 t +1) Quicksort 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. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 498–524, 2001