Name
Abstract | ||
|---|---|---|
Given a set of n elements, each of which is colored one of c colors, we must determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We focus on the expected number of color comparisons when the cn colorings are equally probable. We analyze an obvious algorithm, showing that its expected performance is c2 + c − 2/2c n − O(c2), with variance Θ(c2n). We present and analyze an algorithm for the case c = 3 colors whose average complexity on the 3n equally probable inputs is 7083/5425n + O(&sqrt;n) = 1.3056…n + O(&sqrt; n), substantially better than the expected complexity 5/3n + O(1) = 1.6666…n + O(1) of the obvious algorithm. We describe a similar algorithm for c =4 colors whose average complexity on the 4n equally probable inputs is 761311/402850n + O(log n) = 1.8898…n + O(log n), substantially better than the expected complexity 9/4n + O(1) = 2.25n + O(1) of the obvious algorithm. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1497290.1497293 | ACM Transactions on Algorithms |
Keywords | Field | DocType |
expected performance,average-case analysis,obvious algorithm,similar algorithm,expected number,c color,log n,probable input,average complexity,additional key words and phrases: algorithm analysis,expected complexity,n element,plurality algorithm,plurality problem,majority problem | Discrete mathematics,Binary logarithm,Combinatorics,Colored,Algorithm,Expected value,Majority problem,Mathematics,Case analysis | Journal |
Volume | Issue | ISSN |
5 | 2 | 1549-6325 |
Citations | PageRank | References |
5 | 0.81 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Laurent Alonso | 1 | 10 | 1.79 |
| Edward M. Reingold | 2 | 2214 | 563.65 |