Second phase changes in random \(m\)-ary search trees and generalized quicksort: Convergence rates
From MaRDI portal
Publication:1394520
DOI10.1214/aop/1048516530zbMath1021.60020OpenAlexW1814614163MaRDI QIDQ1394520
Publication date: 20 October 2003
Published in: The Annals of Probability (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1214/aop/1048516530
convergence ratesasymptotic normalityphase changesearch treesmethod of momentslocal limit theoremsquicksort
Related Items
Subtree Sizes in Recursive Trees and Binary Search Trees: Berry–Esseen Bounds and Poisson Approximations ⋮ Dependence and phase changes in random m‐ary search trees ⋮ An asymptotic distribution theory for Eulerian recurrences with applications ⋮ Functional limit theorems for multitype branching processes and generalized Pólya urns. ⋮ Limit theorems for patterns in phylogenetic trees
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Diffusion-limited aggregation on a tree
- The size of random bucket trees via urn models
- Normal convergence problem? Two moments and a recurrence may be the clues
- Large deviations for combinatorial distributions. I: Central limit theorems
- Fourier analysis of distribution functions. A mathematical study of the Laplace-Gaussian law
- Phase changes in randomm-ary search trees and generalized quicksort
- Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
- On the Most Probable Shape of a Search Tree Grown from a Random Permutation
- Combinatorial analysis of quicksort algorithm
- Analysis of the space of search trees under the random insertion algorithm
- Universal Limit Laws for Depths in Random Trees
- The Joint Distribution of Elastic Buckets in Multiway Search Trees
- Limit Laws for Sums of Functions of Subtrees of Random Binary Search Trees
- Quicksort asymptotics
- The Accuracy of the Gaussian Approximation to the Sum of Independent Variates
- Quicksort
