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 language | English |
---|---|
Number of pages | 28 |
Journal | Electronic Journal of Probability |
Volume | 19 |
Issue number | 3 |
DOIs | |
Publication status | Published - 6 Jan 2014 |
Keywords
- FIND algorithm
- Quickselect
- complexity
- key comparisons
- functional limit theorem
- contraction method
- Gaussian process