Reference no: EM131291646

In the 2003 California gubernatorial recall election, the ballot contained 135 candidates, including people with various listings for their current job, including "actor," "comedian," and even "adult film actress." The winner was the actor-businessman Arnold Schwarzenegger, who got over 48% of the vote. Suppose we have the election results from such an election, with a large number, n, of candidates, and the only tool we can use to determine the winner is to encode the names of all the candidates using the Huffman coding algorithm, based on the number of votes each candidate got in this election. Suppose further that a friend of yours is guessing that if the winning candidate gets more than 40% of the votes, then his or her name will be encoded with a single bit. Prove that this conjecture is true and analyze the running time of this election-counting algorithm.