A note on the Quicksort asymptotics

DOI10.1002/RSA.20524MaRDI QIDQ5265342zbMATH OpenOpenAlexFDO

Authors Michael Fuchs

Publication date 23 July 2015

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20524

zbMATH Keywords

central limit theoremQuicksortmoment-transfer approachkey comparisons\(L_{p}\)-distance

Mathematics Subject Classification ID

Martingales with discrete parameter (60G42) Searching and sorting (68P10)

Recommendations

• Exact \(L^2\)-distance from the limit for QuickSort key comparisons (extended abstract).
• Quicksort asymptotics
• QuickSort: improved right-tail asymptotics for the limiting distribution, and large deviations
• A limit theorem for “quicksort”
• Refined quicksort asymptotics

Cites work

• A limiting distribution for quicksort
• An asymptotic theory for Cauchy–Euler differential equations with applications to the analysis of algorithms
• Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
• Quicksort asymptotics
• Rates of convergence for Quicksort
• Transfer theorems and asymptotic distributional results for m‐ary search trees

Cited in

(17)

• On martingale tail sums for the path length in random trees
• Distributional convergence for the number of symbol comparisons used by QuickSort
• Refined asymptotics for the number of leaves of random point quadtrees
• Exact \(L^2\)-distance from the limit for QuickSort key comparisons (extended abstract).
• Asymptotic distributions for random median quicksort
• On martingale tail sums in affine two-color urn models with multiple drawings
• Rates of convergence for Quicksort
• Quicksort asymptotics
• A limit theorem for “quicksort”
• Refined quicksort asymptotics
• scientific article; zbMATH DE number 5568413 (Why is no real title available?)
• Asymptotic analysis of an optimized quicksort algorithm.
• Computing and Combinatorics
• Logarithmic integrals, zeta values, and tiered binomial coefficients
• A note concerning the limit distribution of the quicksort algorithm
• Dependence and phase changes in random \(m\)-ary search trees
• Revisiting calculation of moments of number of comparisons used by the randomized quick sort algorithm

Describes a project that uses

Uses Software

• Quicksort

This page was built for publication: A note on the Quicksort asymptotics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5265342)