The Average-Case Complexity of Determining the Majority

Abstract

Given a set of n elements each of which is either red or blue, it is known that in the worst case $n-\nu(n)$ pairwise equal/not equal color comparisons are necessary and sufficient to determine the majority color, where $\nu(n)$ is the number of 1-bits in the binary representation of n. We prove that $\frac{2n}{3} - \sqrt\frac{8n}{9\pi} + O(\log n)$ such comparisons are necessary and sufficient in the average case.