Results 1 to 2 of 2

Math Help - Majority problem in linear time

  1. #1
    Newbie
    Joined
    Sep 2010
    Posts
    9

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,535
    Thanks
    778
    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.)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: December 14th 2011, 03:32 PM
  2. Replies: 1
    Last Post: August 1st 2011, 06:03 AM
  3. Replies: 4
    Last Post: December 16th 2010, 02:22 PM
  4. sorting fraction with linear time algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 11th 2008, 08:39 PM
  5. Replies: 1
    Last Post: September 29th 2005, 09:47 PM

Search Tags


/mathhelpforum @mathhelpforum