Analysis of Boyer and Moore's MJRTY algorithm

Laurent Alonso (1) , Edward M. Reingold (2)

1 ALICE - Geometry and Lighting
2 IIT CS - Department of Computer Science [IIT]

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)$.

Domaines: Complexité [cs.CC]

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⟩