4 papers
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…