Back to overview

Analysis of Algorithms for Permutations Biased by Their Number of Records

Type of publication Peer-reviewed
Publikationsform Proceedings (peer-reviewed)
Author Auger Nicolas, Bouvel Mathilde, Nicaud Cyril, Pivoteau Carine,
Project Permutation classes: from structure to combinatorial properties
Show all

Proceedings (peer-reviewed)

Title of proceedings Analysis of Algorithms 2016
Place Krakow, Poland

Open Access


The topic of the article is the realistic study of the complexity of algorithms on arrays of pairwise distinct integers. We introduce a model that takes into account the non-uniformness of data, which we call the Ewens-like distribution of parameter theta for records on permutations: the weight theta^r of a permutation depends on its number r of records. We show that this model is meaningful for the notion of presortedness, while still being mathematically tractable. Our results describe the average value of several classical permutation statistics in this model, and give the average running time of three algorithms: the Insertion Sort, and two variants of the Min-Max search.