Chapter 8.3, Problem 17E

Suppose that the votes of n people for different candidates (where there can be more than two candidates) for a particular office are the elements of a sequence. A person wins the election if this person receives a majority of the votes.

Pare 562

a) Devise a divide-and-conquer algorithm that deter- mines whether a candidate received a majority and, if so, determine who this candidate is. [Hint:

Assume that n is even and split the sequence of votes into two sequences, each with $n/2$ elements. Note that a candidate could not have received a majority of votes with- out receiving a majority of votes in at least one of the two halves.]

b) Use the master theorem to give a big-O estimate for the number of comparisons needed by the algorithm you devised in part (a).