Skip to Main content Skip to Navigation
New interface
Journal articles

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)$.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-00926106
Contributor : Laurent Alonso Connect in order to contact the contributor
Submitted on : Thursday, January 9, 2014 - 10:20:43 AM
Last modification on : Friday, November 18, 2022 - 9:25:55 AM
Long-term archiving on: : Thursday, April 10, 2014 - 2:46:04 PM

File

mjrty3.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

118

Files downloads

230