Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
From MaRDI portal
Publication:3149890
DOI10.1137/S009753970138390XzbMath1008.68166OpenAlexW2087183702MaRDI QIDQ3149890
Hsien-Kuei Hwang, Ralph Neininger
Publication date: 29 September 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s009753970138390x
analysis of algorithmscontraction methodmethod of momentslimit distributionbinary search treesquicksort
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Central limit and other weak theorems (60F05) Recurrences (11B37)
Related Items (31)
Distribution of a class of divide and conquer recurrences arising from the computation of the Walsh-Hadamard transform ⋮ Distribution of distances in random binary search trees. ⋮ Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs ⋮ Stochastic analysis of the extra clustering model for animal grouping ⋮ On moment sequences and mixed Poisson distributions ⋮ Cost distribution of the Chang-Roberts leader election algorithm and related problems ⋮ The left-right-imbalance of binary search trees ⋮ Logarithmic integrals, zeta values, and tiered binomial coefficients ⋮ Limit laws for two distance-based indices in random recursive tree models ⋮ Second phase changes in random \(m\)-ary search trees and generalized quicksort: Convergence rates ⋮ Central Limit Theorems for Additive Tree Parameters with Small Toll Functions ⋮ Prediction of group patterns in social mammals based on a coalescent model ⋮ A general limit theorem for recursive algorithms and combinatorial structures ⋮ A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees ⋮ Minimal clade size and external branch length under the neutral coalescent ⋮ Cost functionals for large (uniform and simply generated) random trees ⋮ On statistical tests of phylogenetic tree imbalance: The Sackin and other indices revisited ⋮ Singularity analysis, Hadamard products, and tree recurrences ⋮ The area above the Dyck path of a permutation ⋮ Limiting distributions for additive functionals on Catalan trees ⋮ The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance ⋮ Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton-Watson trees ⋮ Symmetric fixed points of a smoothing transformation ⋮ A central limit theorem for additive functionals of increasing trees ⋮ Limit laws for the Randić index of random binary tree models ⋮ The sum of powers of subtree sizes for conditioned Galton-Watson trees ⋮ Probabilistic analysis of algorithms for the Dutch national flag problem ⋮ Fixed points with finite variance of a smoothing transformation. ⋮ Probabilistic analysis of a genealogical model of animal group patterns ⋮ Limit theorems for patterns in phylogenetic trees ⋮ A note on the quicksort asymptotics
This page was built for publication: Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
