A Gaussian limit process for optimal FIND algorithms

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

External organisations

  • Univ Frankfurt
  • TU Vienna

Abstract

We consider versions of the FIND algorithm where the pivot element used is the median of a subset chosen uniformly at random from the data. For the median selection we assume that subsamples of size asymptotic to c⋅nα are chosen, where 0<α≤12, c>0 and n is the size of the data set to be split. We consider the complexity of FIND as a process in the rank to be selected and measured by the number of key comparisons required. After normalization we show weak convergence of the complexity to a centered Gaussian process as n→∞, which depends on α. The proof relies on a contraction argument for probability distributions on càdlàg functions. We also identify the covariance function of the Gaussian limit process and discuss path and tail properties.

Details

Original languageEnglish
Number of pages28
JournalElectronic Journal of Probability
Volume19
Issue number3
Publication statusPublished - 6 Jan 2014

Keywords

  • FIND algorithm , Quickselect , complexity , key comparisons , functional limit theorem , contraction method , Gaussian process