Search Results

Documents authored by Ischebeck, Jasper

Document
DOI: 10.4230/LIPIcs.AofA.2026.19
Fringe Subtrees of Split Trees

Authors: Cecilia Holmgren, Jasper Ischebeck, and Svante Janson

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract
We consider additive functionals X_n(ϕ) with small toll functions on split trees and a generalization of split trees, which we call fractional split trees, where the split vector does not need to sum up to 1. These additive functionals encompass e.g. the number of nodes, number of leaves and the number of fringe trees of a certain size. We show convergence of the first moment to a limit, which we can explicitly compute if all balls are distributed multinomially and for some models with Beta-distributed splitter. Generally, the first moment is given in terms of negative moments of a perpetuity and can often be approximated to arbitrary precision with known bounds. In split trees and certain fractional split trees, the standard deviation is of smaller order than the first moment, where we show a weak law of large numbers. In other fractional split trees, the standard deviation is of the same order and we show a distribution limit using the contraction method.
Cite as

Cecilia Holmgren, Jasper Ischebeck, and Svante Janson. Fringe Subtrees of Split Trees. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{holmgren_et_al:LIPIcs.AofA.2026.19,
  author =	{Holmgren, Cecilia and Ischebeck, Jasper and Janson, Svante},
  title =	{{Fringe Subtrees of Split Trees}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.19},
  URN =		{urn:nbn:de:0030-drops-262900},
  doi =		{10.4230/LIPIcs.AofA.2026.19},
  annote =	{Keywords: fringe tree, split tree, fractional split tree, limit theorem, additive functional, renewal theory, Fourier series}
}
Document
DOI: 10.4230/LIPIcs.AofA.2026.22
A Distributional Analysis of QuickXsort for Mergesort

Authors: Jasper Ischebeck, Florian Lesny, and Ralph Neininger

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract
QuickXsort is an efficient in situ sequential sorting algorithm that mixes Hoare’s Quicksort algorithm with another sorting algorithm X, such as Heapsort, Insertionsort or Mergesort. The advantage is that QuickXsort can be in-place even if X is not. QuickXsort works recursively like Quicksort but uses sorting algorithm X on one of the sub-lists generated in each step. While the expected complexity of QuickXsort, measured by the number of key comparisons, has been investigated for various choices of X, here the asymptotic variance and distribution of the normalized complexity are studied with Mergesort used as X. Various versions of Mergesort and splitting regimes for the decomposition of the list by Quicksort are considered and periodicities in moments and the distributions are characterized.
Cite as

Jasper Ischebeck, Florian Lesny, and Ralph Neininger. A Distributional Analysis of QuickXsort for Mergesort. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ischebeck_et_al:LIPIcs.AofA.2026.22,
  author =	{Ischebeck, Jasper and Lesny, Florian and Neininger, Ralph},
  title =	{{A Distributional Analysis of QuickXsort for Mergesort}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.22},
  URN =		{urn:nbn:de:0030-drops-262932},
  doi =		{10.4230/LIPIcs.AofA.2026.22},
  annote =	{Keywords: QuickXsort, Analysis of Algorithms, Mergesort, distribution analysis, limit law, weak convergence, contraction method}
}
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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact