A limiting distribution for quicksort
From MaRDI portal
Publication:3833634
DOI10.1051/ITA/1989230303351zbMath0677.68072OpenAlexW1490652101MaRDI QIDQ3833634
Publication date: 1989
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/92338
Related Items (43)
Distribution of a class of divide and conquer recurrences arising from the computation of the Walsh-Hadamard transform ⋮ The Weighted Branching Process ⋮ Some properties of a limiting distribution in Quicksort ⋮ Logarithmic integrals, zeta values, and tiered binomial coefficients ⋮ Average-case analysis of multiple Quickselect: An algorithm for finding order statistics ⋮ Running time of the treapsort algorithm ⋮ Analyzing randomized search heuristics via stochastic domination ⋮ Unnamed Item ⋮ Analysis of quickselect : an algorithm for order statistics ⋮ Balancing \(m\)-ary search trees with compressions on the fringe ⋮ Almost sure convergence to the quicksort process ⋮ General Edgeworth expansions with applications to profiles of random trees ⋮ The quicksort process ⋮ Distributional convergence for the number of symbol comparisons used by QuickSort ⋮ 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 ⋮ Automatic average-case analysis of algorithms ⋮ 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 ⋮ Cost functionals for large (uniform and simply generated) random trees ⋮ Distances in random plane-oriented recursive trees ⋮ General combinatorial schemas: Gaussian limit distributions and exponential tails ⋮ The total path length of split trees ⋮ On martingale tail sums for the path length in random 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 ⋮ A limit theorem for “quicksort” ⋮ On the silhouette of binary search trees ⋮ On weighted depths in random binary search trees ⋮ On the internal path length ofd-dimensional quad trees ⋮ An almost sure result for path lengths in binary search trees ⋮ A note concerning the limit distribution of the quicksort algorithm ⋮ Stochastic fixed-point equations ⋮ Upper tail analysis of bucket sort and random tries ⋮ Upper tail analysis of bucket sort and random tries ⋮ QuickSort: improved right-tail asymptotics for the limiting distribution, and large deviations ⋮ Combinatorial analysis of quicksort algorithm ⋮ Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect ⋮ A note on the quicksort asymptotics
Uses Software
Cites Work
This page was built for publication: A limiting distribution for quicksort
