Filtern
Erscheinungsjahr
- 2014 (1)
Dokumenttyp
Sprache
- Englisch (1)
Volltext vorhanden
- ja (1)
Gehört zur Bibliographie
- nein (1)
Schlagworte
- complexity (1) (entfernen)
Institut
- 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.