THE AVERAGE-CASE COMPLEXITY OF DETERMINING THE MAJORITY

Authors
ALONSO L REINGOLD EM SCHOTT R
Citation
L. Alonso et al., THE AVERAGE-CASE COMPLEXITY OF DETERMINING THE MAJORITY, SIAM journal on computing, 26(1), 1997, pp. 1-14
Citations number
11
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
26
Issue
1
Year of publication
1997
Pages
1 - 14
Database
ISI
SICI code
0097-5397(1997)26:1<1:TACODT>2.0.ZU;2-1
Abstract
Given a set of n elements each of which is either red or blue, it is k nown that in the worst case n - v(n) pairwise equal/not equal color co mparisons are necessary and sufficient to determine the majority color , where v(n) is the number of 1-bits in the binary representation of n . We prove that 2n/3 - root 8n/9 pi + O(log n) such comparisons are ne cessary and sufficient in the average case.