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

DOI10.1016/J.DAM.2005.07.005zbMATH Open1083.68149DBLPjournals/dam/Dean06OpenAlexW2050001863WikidataQ30000112 ScholiaQ30000112MaRDI QIDQ2581554FDOQ2581554

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

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

zbMATH Keywords

QuicksortDivide and conquerProbabilistic recurrence

Mathematics Subject Classification ID

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

Cites Work

• Quicksort
• Introduction to algorithms

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

Uses Software

• Quicksort
• Find

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)