DETERMINING THE MAJORITY

Authors
ALONSO L REINGOLD EM SCHOTT R
Citation
L. Alonso et al., DETERMINING THE MAJORITY, Information processing letters, 47(5), 1993, pp. 253-255
Citations number
5
Categorie Soggetti
Information Science & Library Science","Computer Applications & Cybernetics
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
47
Issue
5
Year of publication
1993
Pages
253 - 255
Database
ISI
SICI code
0020-0190(1993)47:5<253:DTM>2.0.ZU;2-T
Abstract
Given a set of n elements each of which is either red or blue, it is k nown that n-nu(n) pairwise equal/not equal colour comparisons are nece ssary and sufficient to determine the majority color, where nu(n) is t he number of 1-bits in the binary representation of n. We present a ne w, simple proof of this lower bound.