Skip to Main content Skip to Navigation
Journal articles

Analysis of Boyer and Moore's MJRTY algorithm

Laurent Alonso 1 Edward 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 <>
Submitted on : Thursday, January 9, 2014 - 10:20:43 AM
Last modification on : Wednesday, July 28, 2021 - 4:58:02 PM
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 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⟩

Share

Metrics

Record views

325

Files downloads

649