6 papers · 1 filter
Probabilistic analysis of optimal multi-pivot QuickSort
Cecilia Holmgren, Jasper Ischebeck, Daniel Krenn +2
We consider a multi-pivot QuickSort algorithm using pivot elements to partition a nonsorted list into sublists in order to proceed recursively on these subli…
Fringe subtrees of split trees and fractional split trees
Cecilia Holmgren, Jasper Ischebeck, Svante Janson
We consider additive functionals with small toll functions on split trees and a generalization of split trees, which we call fractional split trees, where the split vecto…
Central limit theorems for additive functionals in patricia tries
Jasper Ischebeck
We give theorems about asymptotic normality of general additive functionals on patricia tries in an i.i.d. setting, derived from results on tries by Janson (2022). These theorems a…
On fine fluctuations of the complexity of the QuickSelect algorithm
Jasper Ischebeck, Ralph Neininger
The Quickselect algorithm (also called FIND) is a fundamental algorithm for selecting ranks or quantiles within a set of data. Grübel and Rösler showed that the number of key com…
Ancestral reproductive bias in continuous time branching trees under various sampling schemes
Jan Lukas Igelbrink, Jasper Ischebeck
Cheek and Johnston (Journal of Mathematical Biology, 2023) consider a continuous-time Bienaymé-Galton-Watson tree conditioned on being alive at time . They study the reproducti…
Patricia's Bad Distributions
Louigi Addario-Berry, Pat Morin, Ralph Neininger
The height of a random PATRICIA tree built from independent, identically distributed infinite binary strings with arbitrary diffuse probability distribution on $\{0,1\}^\mathb…