60C05 Combinatorial probability
Refine
Year of publication
- 2014 (1)
Document Type
- Article (1)
Language
- English (1)
Has Fulltext
- yes (1)
Is part of the Bibliography
- no (1)
Keywords
- FIND algorithm (1)
- Gaussian process (1)
- Quickselect (1)
- complexity (1)
- contraction method (1)
- functional limit theorem (1)
- key comparisons (1)
Institute
- Mathematik (1)
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.
