TY  - JOUR
A1  - Sulzbach, Henning
A1  - Neininger, Ralph
A1  - Drmota, Michael
T1  - A Gaussian limit process for optimal FIND algorithms
T2  - Electronic journal of probability
N2  - 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.
KW  - FIND algorithm
KW  - Quickselect
KW  - complexity
KW  - key comparisons
KW  - functional limit theorem
KW  - contraction method
KW  - Gaussian process
Y1  - 2014
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/32751
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30:3-327510
SN  - 1083-6489
N1  - This work is licensed under a Creative Commons Attribution 3.0 License. http://creativecommons.org/licenses/by/3.0/
VL  - 19
IS  - 3
ER  -