A simple expected running time analysis for randomized ``divide and conquer algorithms

DOI10.1016/J.DAM.2005.07.005MaRDI QIDQ2581554zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Brian C. Dean

Publication date 10 January 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2005.07.005

zbMATH Keywords

QuicksortDivide and conquerProbabilistic recurrence

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) Searching and sorting (68P10)

Recommendations

• On the analysis of stochastic divide and conquer algorithms
• The solution of linear probabilistic recurrence relations
• Probabilistic recurrence relations
• QUICKSELECT revisited
• Asymptotic distributions for random median quicksort

Cites work

• Introduction to algorithms
• Quicksort

Cited in

(10)

• The solution of linear probabilistic recurrence relations
• Average running time analysis of an algorithm to calculate the size of the union of Cartesian products.
• On the analysis of stochastic divide and conquer algorithms
• An intuitive and simple bounding argument for Quicksort
• Automated recurrence analysis for almost-linear expected-runtime bounds
• Probabilistic recurrence relations
• Group testing: revisiting the ideas
• On the average time complexity of computation with random partition
• \texttt{tttplots-compare}: a Perl program to compare time-to-target plots or general runtime distributions of randomized algorithms
• The worst-case running time of the random simplex algorithm is exponential in the height

Describes a project that uses

Uses Software

• Find
• Quicksort

This page was built for publication: A simple expected running time analysis for randomized ``divide and conquer algorithms

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