DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2024.9

On Fluctuations of Complexity Measures for the FIND Algorithm

Authors: Jasper Ischebeck and Ralph Neininger

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract

The FIND algorithm (also called Quickselect) is a fundamental algorithm to select ranks or quantiles within a set of data. It was shown by Grübel and Rösler that the number of key comparisons required by FIND as a process of the quantiles α ∈ [0,1] in a natural probabilistic model converges after normalization in distribution within the càdlàg space D[0,1] endowed with the Skorokhod metric. We show that the process of the residuals in the latter convergence after normalization converges in distribution to a mixture of Gaussian processes in D[0,1] and identify the limit’s conditional covariance functions. A similar result holds for the related algorithm QuickVal. Our method extends to other cost measures such as the number of swaps (key exchanges) required by FIND or cost measures which are based on key comparisons but take into account that the cost of a comparison between two keys may depend on their values, an example being the number of bit comparisons needed to compare keys given by their bit expansions.

Cite as

Jasper Ischebeck and Ralph Neininger. On Fluctuations of Complexity Measures for the FIND Algorithm. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ischebeck_et_al:LIPIcs.AofA.2024.9,
  author =	{Ischebeck, Jasper and Neininger, Ralph},
  title =	{{On Fluctuations of Complexity Measures for the FIND Algorithm}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.9},
  URN =		{urn:nbn:de:0030-drops-204440},
  doi =		{10.4230/LIPIcs.AofA.2024.9},
  annote =	{Keywords: FIND, Quickselect, rank selection, probabilistic analysis of algorithms, weak convergence, functional limit theorem}
}

Search Results

Documents authored by Ischebeck, Jasper

On Fluctuations of Complexity Measures for the FIND Algorithm

Abstract

Cite as

Thanks for your feedback!

Could not send message