A Gaussian limit process for optimal FIND algorithms

Henning Sulzbach, Ralph Neininger, Michael Drmota

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)
132 Downloads (Pure)

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.
Original languageEnglish
Number of pages28
JournalElectronic Journal of Probability
Volume19
Issue number3
DOIs
Publication statusPublished - 6 Jan 2014

Keywords

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

Fingerprint

Dive into the research topics of 'A Gaussian limit process for optimal FIND algorithms'. Together they form a unique fingerprint.

Cite this