Average-Case Analysis of Some Plurality Algorithms

Laurent Alonso 1 Edward M. Reingold 2
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.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal.inria.fr/inria-00325044
Contributeur : Laurent Alonso <>
Soumis le : vendredi 26 septembre 2008 - 07:59:57
Dernière modification le : jeudi 11 janvier 2018 - 06:20:18

Lien texte intégral

Identifiants

Collections

Citation

Laurent Alonso, Edward M. Reingold. Average-Case Analysis of Some Plurality Algorithms. ACM Transactions on Algorithms, Association for Computing Machinery, 2009, 5 (2), 〈http://portal.acm.org/ft_gateway.cfm?id=1497293&type=pdf&coll=GUIDE&dl=GUIDE&CFID=68819978&CFTOKEN=54725410〉. 〈10.1145/1497290.1497293〉. 〈inria-00325044〉

Partager

Métriques

Consultations de la notice

205