QUICKSELECT Revisited

Author

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

Volume 3, Issue 2
November 2004
Pages 271-296
  • Receive Date: 23 July 2022
  • Revise Date: 25 May 2024
  • Accept Date: 23 July 2022