文摘
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 comparisons to determine the majority color. We analyze the average behavior of their algorithm, proving that if all possible inputs are equally likely, the average number of color comparisons used is with variance .