Analysis of Boyer and Moore's MJRTY algorithm

Laurent Alonso 1 Edward M. Reingold 2
1 ALICE - Geometry and Lighting
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : Given a set of $n$ elements each of which is either red or blue, Boyer and Moore's MJRTY algorithm uses pairwise equal/not equal color comparison to determine the majority color. We analyze the average behavior of their algorithm, proving that if all $2^n$ possible inputs are equally likely, the average number of color comparisons used is $n-\sqrt{2n/\pi} + O(1)$ with variance $(\pi-2)n/\pi - \sqrt{2n/\pi} + O(1)$.
Type de document :
Article dans une revue
Information Processing Letters, Elsevier, 2013, 113, pp.495-497. 〈10.1016/j.ipl.2013.04.005〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00926106
Contributeur : Laurent Alonso <>
Soumis le : jeudi 9 janvier 2014 - 10:20:43
Dernière modification le : jeudi 11 janvier 2018 - 06:25:23
Document(s) archivé(s) le : jeudi 10 avril 2014 - 14:46:04

Fichier

mjrty3.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Laurent Alonso, Edward M. Reingold. Analysis of Boyer and Moore's MJRTY algorithm. Information Processing Letters, Elsevier, 2013, 113, pp.495-497. 〈10.1016/j.ipl.2013.04.005〉. 〈hal-00926106〉

Partager

Métriques

Consultations de la notice

162

Téléchargements de fichiers

269