A note on the Quicksort asymptotics

DOI10.1002/RSA.20524zbMATH Open1332.68039OpenAlexW2070764111MaRDI QIDQ5265342FDOQ5265342

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (16)

• A limit theorem for “quicksort”
• Title not available (Why is that?)
• A note concerning the limit distribution of the quicksort algorithm
• Asymptotic distributions for random median quicksort
• Dependence and phase changes in random m‐ary search trees
• Logarithmic integrals, zeta values, and tiered binomial coefficients
• Distributional convergence for the number of symbol comparisons used by QuickSort
• Title not available (Why is that?)
• On martingale tail sums in affine two-color urn models with multiple drawings
• On martingale tail sums for the path length in random trees
• Asymptotic analysis of an optimized quicksort algorithm.
• Revisiting calculation of moments of number of comparisons used by the randomized quick sort algorithm
• Refined quicksort asymptotics
• Computing and Combinatorics
• Quicksort asymptotics
• Rates of convergence for Quicksort

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)