Author

• Uwe R¨osler

Abstract

We give an overview of the running time analysis of the random divide-and-conquer algorithm FIND or QUICKSELECT. The results concern moments, distribution of FIND’s running time, the limiting distribution, a stochastic bound and the key: a stochastic fixed point equation.

Keywords

• Analysis of algorithms
• asymptotic distribution
• FIND
• FIND process
• quickselect
• stochastic algorithm
• stochastic fixed point equation