Refined quicksort asymptotics
From MaRDI portal
Publication:4982619
DOI10.1002/rsa.20497zbMath1327.68086arXiv1207.4556OpenAlexW2157848365MaRDI QIDQ4982619
Publication date: 9 April 2015
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1207.4556
complexityrate of convergencecentral limit theoremcontraction methodstrong limit theoremQuicksortkey comparisonsZolotarev metric
Central limit and other weak theorems (60F05) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (9)
Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs ⋮ Weakly protected nodes in random binary search trees ⋮ Logarithmic integrals, zeta values, and tiered binomial coefficients ⋮ Unnamed Item ⋮ Edgeworth expansions for profiles of lattice branching random walks ⋮ Refined asymptotics for the composition of cyclic urns ⋮ Dependence and phase changes in random m‐ary search trees ⋮ On martingale tail sums for the path length in random trees ⋮ On martingale tail sums in affine two-color urn models with multiple drawings
Uses Software
Cites Work
- Unnamed Item
- Trickle-down processes and their boundaries
- A general limit theorem for recursive algorithms and combinatorial structures
- A functional limit theorem for the profile of search trees
- Exact L^2-distance from the limit for QuickSort key comparisons (extended abstract)
- Approximation of Distributions of Sums of Independent Random Variables with Values in Infinite-Dimensional Spaces
- Ideal Metrics in the Problem of Approximating Distributions of Sums of Independent Random Variables
- Quicksort asymptotics
- Rates of convergence for Quicksort
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
This page was built for publication: Refined quicksort asymptotics
