Paweł Gawrychowski · Jukka Suomela · Przemysław Uznański

Randomized algorithms for finding a majority element

SWAT 2016 · Scandinavian Symposium and Workshops on Algorithm Theory, Reykjavik, Iceland, June 2016 · doi:10.4230/LIPIcs.SWAT.2016.9

authors’ version publisher’s version arXiv.org

Abstract

Given $n$ colored balls, we want to detect if more than $\lfloor n/2\rfloor$ of them have the same color, and if so find one ball with such majority color. We are only allowed to choose two balls and compare their colors, and the goal is to minimize the total number of such operations. A well-known exercise is to show how to find such a ball with only $2n$ comparisons while using only a logarithmic number of bits for bookkeeping. The resulting algorithm is called the Boyer–Moore majority vote algorithm. It is known that any deterministic method needs $\lceil 3n/2\rceil-2$ comparisons in the worst case, and this is tight. However, it is not clear what is the required number of comparisons if we allow randomization. We construct a randomized algorithm which always correctly finds a ball of the majority color (or detects that there is none) using, with high probability, only $7n/6+o(n)$ comparisons. We also prove that the expected number of comparisons used by any such randomized method is at least $1.038n$.

Publication

Rasmus Pagh (Ed.): 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:14, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2016

ISBN 978-3-95977-011-8

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.