Boyer–Moore majority vote algorithm

It is not possible for a streaming algorithm to find the most frequent element in less than linear space, for sequences whose number of repetitions can be small.

However, it is possible to perform a second pass over the same input sequence in order to count the number of times the reported element occurs and determine whether it is actually a majority.

In the random access model of computing usually used for the analysis of algorithms, each of these values can be stored in a machine word and the total space needed is O(1).

If an array index is needed to keep track of the algorithm's position in the input sequence, it doesn't change the overall constant space bound.

The algorithm's bit complexity (the space it would need, for instance, on a Turing machine) is higher, the sum of the binary logarithms of the input length and the size of the universe from which the elements are drawn.

The state of the Boyer–Moore algorithm after each input symbol. The inputs are shown along the bottom of the figure, and the stored element and counter are shown as the symbols and their heights along the black curve.