# Average-Case Analysis of Some Plurality Algorithms

1 ALICE - Geometry and Lighting
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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 $c^n$ colorings are equally probable. We analyze an obvious algorithm, showing that its expected performance is $\frac{c^2 + c - 2}{2c} n - O(c^2)$, with variance $\Theta(c^2 n)$. We present and analyze an algorithm for the case $c=3$ colors whose average complexity on the $3^n$ equally probable inputs is $\frac{7083}{5425} n + O(\sqrt n) = 1.3056\cdots n + O(\sqrt n)$, substantially better than the expected complexity $\frac{5}{3} n + O(1) = 1.6666\cdots n + O(1)$ of the obvious algorithm. We describe a similar algorithm for $c=4$ colors whose average complexity on the $4^n$ equally probable inputs is $\frac{761311}{402850} n + O(\log n)= 1.8898\cdots n + O(\log n)$, substantially better than the expected complexity $\frac{9}{4} n + O(1) = 2.25 n + O(1)$ of the obvious algorithm.
Keywords :
Document type :
Journal articles

https://hal.inria.fr/inria-00325044
Contributor : Laurent Alonso <>
Submitted on : Friday, September 26, 2008 - 7:59:57 AM
Last modification on : Friday, February 26, 2021 - 3:28:08 PM

### Citation

Laurent Alonso, Edward M. Reingold. Average-Case Analysis of Some Plurality Algorithms. ACM Transactions on Algorithms, Association for Computing Machinery, 2009, 5 (2), ⟨10.1145/1497290.1497293⟩. ⟨inria-00325044⟩

Record views