Thread: Majority problem in linear time

Hello.

I have been asked to create a linear time solution to the majority/majority vote problem stated as follows:
in a set of n elements if there are more than n/2 identical elements, they constitute a majority. Eg in xyxx the majority is x. I understand the Boyer-Moore solution but not its proof.

I am looking to solve the problem by perhaps finding a fast way of determining if an element is -not- part of the majority and elliminating those. My question is how I should formulate the base case for this algorithm on which to build an inductive solution. The way I see it there are at least 3 possible combinations in the smallest case:
xxy
xyx
yxx

I am looking to solve the problem by perhaps finding a fast way of determining if an element is -not- part of the majority and elliminating those.

I am not sure if you are want to come up with a different algorithm from Boyer-Moore. Why would that be necessary? It is most likely easier to understand the proof of the existing algorithm than to create a new one.

I understand the Boyer-Moore solution but not its proof.

What exactly do you not understand? Here is the authors' description and proof. (You can convert a PS file to PDF here.)