Divide-and-conquer: Determining the top two candidates and whether these two candidates received more than n/2 votes

Question

Suppose that each person in a group of n people votes for exactly two people from a set of candidates to fill two positions on a committee. The top two finishers both win positions as long as each receives more than n/2 votes.

Describe a divide-and-conquer algorithm that determines the top two candidates and whether these two candidates received more than n/2 votes.

I have the answer (below), but there's one part I don't understand:

Our algorithm will take a sequence of 2n names (two different names provided by each of n voters) and determine whether the two top vote-getters occur on our list more than n/2 times, and if so, who they are. Actually for technical reasons we will need the top 3 vote-getters.** The votes of each voter are adjacent. Note that we can have at most 3 people (but not 4) with more than half of the votes. Divide the list into two parts, the first half and the second half. (No one could have gotten more than n/2 votes on this list without having more than half votes in one half or the other, since if a candidate got less than or equal to half the votes in each half, then he got less than or equal to half the votes in all.) Thus apply the algorithm recursively to each half to come up with at most six names (three from each half). Then run through the entire list to count the number of occurrences of each of these names to decide which, if any, are the winners. This requires at most 12n additional comparisons for a list of length 2n.

---

I don't understand why we are coming up with at most six names. I also don't get where the 12n comes from. To be more clear, I sort of understand why the 12n is a thing given the 6 names, but I don't understand why it's 6, and if it means 6 names for each step of recursion, or 6 names after all of the recursion (and if the latter, what happens during each step of recursion?).

Answer 1

The original problem is not quoted/rephrased correctly

Here is one correct version as it appears as exercise 18 in section 8.3 of the book Discrete Mathematics and Its Applications, 7th Edition by Kenneth H. Rosen, with slight modification.

Suppose that each person in a group of $n$ people votes for exactly two people from a set of candidates to fill two positions on a committee. The top two finishers both win positions as long as each receives more than $n/2$ votes.
Devise a divide-and-conquer algorithm that determines whether the two candidates who received the most votes each received more than $n/2$ votes. If so, determine who these two candidates are.

What is difference? As I have emphasized, only when it has been determined that each of the two candidates who received the most votes (the top two candidates) has received more than $n/2$ votes, the desired algorithm is required to determine these two candidates . In other word, if it has been determined that at least one of the top two candidates received at most $n/2$ votes, the algorithm is not required to determine these candidates.

The catch here is that it is possible to determine whether the top candidate received more than $n/2$ vote without identifying who is the top candidate. It is also possible to determine whether the second top candidate received more than $n/2$ vote without identifying who is the second candidate. For example, if we are able to ascertain the most votes received by any single candidate is at most $n/2$, which can happen when we have checked enough but not all of the votes (so we might not be able to identify who are the top candidates), then we are sure that none of the top two candidates received more than $n/2$ votes.

On the other hand, by its very nature, any (usual) divide-and-conquer algorithm cannot find the top (two) candidates unconditionally. The idea is that it can happen that the top candidates overall is not among the top candidates in either half of the list. In fact, it can happen that the top candidate overall is the bottom candidate in each half of the list. For example, 10 people can vote in the following way, $(A,B), (A,B), (A,B), (C,D), C,D), (E,F), (E,F), (E,F), (C,D), (C,D)$. While $C$ and $D$ are the top candidates overall, they are the bottom candidates voted by the first 5 people and they are the bottom candidates voted by the other 5 people.

---

The "answer" given by the OP, the fourth paragraph in the question, which starts with "our algorithm" and ends before the separator line, is in fact a part of an answer key. For brevity, I will refer to it as "the answer key".

How to understand the answer key

You can check the other cool answer written by D.W., which includes a very detailed analysis of the answer key.

D.W.'s answer describes in great detail, according to the answer key, an algorithm that returns a list of three candidates which contains all the candidates who got more than $n/2$ votes and possibly other candidates. More specifically, if a candidate got more than $n/2$ votes, then he/she must be in the returned list. However, the list may contain people who did not get more than $n/2$ votes. It can also happen that none of the people in the returned list is the top candidate, or the second top candidate, or the third top candidate.

D.W.'s answer also explains clearly "why we are coming up with at most six names" as well as "where the $12n$ comes from".

I have confirmed that D.W.'s algorithm is correct (since he, in his modest way, claim he does not "know whether this algorithm is actually correct") in that it conforms to the answer key and it is a full answer to the original problem except it omits the easy steps such as "if so, determines who these two candidates are".

A better written problem

It turns out, as you must have noticed by now, somewhat subtle to understand exactly what is the requirement of the original problem. Here is my version of the problem that should be much clearer, at least for me.

Suppose that each person in a group of $n$ people votes for exactly two people from a set of candidates. Devise a divide-and-conquer algorithm that determines all candidates who received more than $n/2$ votes.

If you are careful, you may point out the my version missed "... to fill two positions on a committee. The top two finishers both win positions as long as each receives more than n/2 votes". Well, although it is interesting to know that election goal and election rule, it has nothing to do with the specification of the desired algorithm. You may also point out that my version does not require "if so, determine who these two candidates are". Well, if we have determined all candidates who received more than n/2 votes, the number of whom is at most 3, then by just counting the number of votes received by each of those candidates, we can, easily, "if so, determine who these two candidates are".

An interesting algorithm as an exercise

There is an algorithm using linear time and constant space that determines all candidates who received more than $n/2$ votes. The construction of such an algorithm is left as an intriguing and challenging exercise for the readers who has read thus far.

Thanks to Tom van der Zanden, who pointed out a typo in my previous formulation of the exercise.

Answer 2

I can understand why you are finding this unclear. The sketch of a solution that you quote is pretty sparse, and it leaves it to you to fill in details. Here is how I interpret the proposed algorithm:

Algorithm $F[1..n][1..2]$):
1. If $n=1$, return $\{A[1][1], A[1][2]\}$. Otherwise:
2. Set $S_L := F(A[1..n/2][1..2])$ and $S_R := F(A[n/2+1..n][1..2])$ and $S := S_L \cup S_R$.
3. For each $x \in S$, count the number of times that $x$ appears in $A[1..n][1..2]$ and sort the $x$'s by that count.
4. Return the three values that occur the most often in $S$ (breaking ties arbitrarily).

where $A[i][1]$ denotes the first vote from the $i$th voter and $A[i][2]$ the second vote from the $i$th voter. At the end, after running $F(A[1..n][1..2])$, we take the three values returned by this algorithm and check which (if any of them) have received at least $n/2$ votes.

The running time of this algorithm satisfies the recurrence relation

$$T(n) = 2 T(n/2) + O(n).$$

(Why? It's easy to see that $F$ returns at most 3 elements, so $|S| \le 6$. Each iteration of step 3 can be done in $O(n)$ time, and we do only $6=O(1)$ iterations of the loop, so the total running time for steps 3 and 4 is $O(n)$.) This recurrence solves to $T(n) = O(n \log n)$.

So, this gives an $O(n \log n)$ time algorithm for the problem.

I don't know whether this algorithm is actually correct. I'm just trying to explain what algorithm I believe they are proposing, and to explain their running time analysis. I haven't tried to prove the algorithm correct. The solution you listed appears to sketch the key ideas behind such a proof (or, at least that's the claim). I haven't tried to fill in the details and verify carefully that the proof works out, so you should do that if you care, but it looks plausible to me -- all the ideas make sense to me.

Now, to answer your questions: The reason we come up with only 6 names is that each recursive call returns at most 3 names, and we perform two recursive calls, so we end up with at most $3+3=6$ different names in $S$. Why $12n$? Because each iteration of the loop in step 3 takes $2n$ comparisons (you compare $x$ to each element of $A[1..n][1..2]$, and there are $2n$ such elements), and you do at most 6 iterations of the loop, so the total number of comparisons in step is at most $6 \times 2n = 12n$.

I hope this answers your questions and makes the proposed solution clearer.