A limit theorem for “quicksort”

DOI10.1051/ita/1991250100851zbMath0718.68026OpenAlexW1511251174MaRDI QIDQ5750394

Publication date: 1991

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92383

zbMATH Keywords

Quicksort

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items

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., Limit laws for partial match queries in quadtrees, Weakly protected nodes in random binary search trees, One-sided variations on binary search trees, On Tail Bounds for Random Recursive Trees, On the contraction method with degenerate limit equation., The Weighted Branching Process, Distances in random digital search trees, Some properties of a limiting distribution in Quicksort, Inversions in split trees and conditional Galton--Watson trees, The left-right-imbalance of binary search trees, Squaring within the Colless index yields a better balance index, Thin tails of fixed points of the nonhomogeneous smoothing transform, Logarithmic integrals, zeta values, and tiered binomial coefficients, Average-case analysis of multiple Quickselect: An algorithm for finding order statistics, Higher moments of Banach space valued random variables, A limit process for partial match queries in random quadtrees and 2-d trees, Limit laws for two distance-based indices in random recursive tree models, On the size of paged recursive trees, Unnamed Item, Fixed points of the smoothing transform: two-sided solutions, Analysis of quickselect : an algorithm for order statistics, DEGREE PROFILE OF HIERARCHICAL LATTICE NETWORKS, Almost sure convergence to the quicksort process, Analysis of a drop-push model for percolation and coagulation, General Edgeworth expansions with applications to profiles of random trees, The quicksort process, Distributional convergence for the number of symbol comparisons used by QuickSort, Limit distribution of the quartet balance index for Aldous’s $(\beta \ge 0)$-model, Exact and approximate limit behaviour of the Yule tree's cophenetic index, Analysis of the expected number of bit comparisons required by quickselect, On densities for solutions to stochastic fixed point equations, On the tails of the limiting QuickSort density, On the number of jumps of random walks with a barrier, A general limit theorem for recursive algorithms and combinatorial structures, Minimal clade size and external branch length under the neutral coalescent, Search trees: metric aspects and strong limit theorems, Random binary trees: from the average case analysis to the asymptotics of distributions, On the number of segregating sites for populations with large family sizes, On the Variety of Shapes on the Fringe of a Random Recursive Tree, Asymptotic distributions for random median quicksort, Unnamed Item, Unnamed Item, A fixed point theorem for distributions, Asymptotic Properties of a Leader Election Algorithm, Cost functionals for large (uniform and simply generated) random trees, General combinatorial schemas: Gaussian limit distributions and exponential tails, Perpetuities in Fair Leader Election Algorithms, The functional equation of the smoothing transform, The total path length of split trees, Distributional analysis of swaps in quick select, On martingale tail sums for the path length in random trees, On statistical tests of phylogenetic tree imbalance: The Sackin and other indices revisited, Limiting distributions for additive functionals on Catalan trees, On the number of iterations required by Von Neumann addition, Approximating the limiting Quicksort distribution, On a multivariate contraction method for random recursive structures with applications to Quicksort, On the silhouette of binary search trees, On stochastic recursive equations of sum and max type, A limit field for orthogonal range searches in two-dimensional random point search trees, The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance, Asymptotic joint normality of counts of uncorrelated motifs in recursive trees, On weighted depths in random binary search trees, On the internal path length ofd-dimensional quad trees, All solutions of the stochastic fixed point equation of the Quicksort process, An almost sure result for path lengths in binary search trees, Limit laws for the Randić index of random binary tree models, Inversions in Split Trees and Conditional Galton–Watson Trees, A note concerning the limit distribution of the quicksort algorithm, Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey, One-sided variations on interval trees, Stochastic fixed-point equations, Convergence of the population dynamics algorithm in the Wasserstein metric, QuickSort: improved right-tail asymptotics for the limiting distribution, and large deviations, Partial match queries in random quadtrees, Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect, Limit Theorems for Depths and Distances in Weighted Random B-Ary Recursive Trees, Limit distribution of distances in biased random tries, Random additions in urns of integers, On weighted branching processes in random environment., The dual tree of a recursive triangulation of the disk, Probabilistic analysis of a genealogical model of animal group patterns, The Smoothing Transform: A Review of Contraction Results, On a functional contraction method, Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm, On binary search tree recursions with monomials as toll functions

Uses Software

Quicksort

Cites Work