3531 articles – 5253 references  [version française]

inria-00325044, version 1

Average-Case Analysis of Some Plurality Algorithms

Laurent Alonso () 1, Edward M. Reingold 2

ACM Transactions on Algorithms 5, 2 (2009)

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.

• 1:  ALICE (INRIA Lorraine - LORIA)
• INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
• 2:  Department of Computer Science [IIT] (IIT CS)
• Illinois Institute of Technology
• Domain : Computer Science/Data Structures and Algorithms
• Keywords : algorithm analysis – majority problem – plurality problem

• inria-00325044, version 1
• oai:hal.inria.fr:inria-00325044
• From:
• Submitted on: Friday, 26 September 2008 07:59:57
• Updated on: Friday, 18 December 2009 11:24:41