Given a set of n elements each of which is either red or blue, it is known that in the worst case n-ν(n) pairwise equal/not equal color comparisons are necessary and sufficient to determine the majority color, where ν(n) is the number of 1-bits in the binary representation of n. We prove that 2n/3 - √8n/9π + O(log n) such comparisons are necessary and sufficient in the average case.
No takes yet. Share an insight, caveat, or question.
Alonso et al. (1997) studied this question.