1. Many meetings
Here is a DivideAndConquer approach:
- Split the ambassadors into two groups of size n/2 each.
In round i, where 1 <= i <= n/2, have the j-th ambassador from the first group meet with the ambassador with index (j+i) mod n/2 in the second group.
- Apply the algorithm recursively to generate schedules for the ambassadors to meet all other ambassadors in their own group, starting in round n/2+1.
- Merge the two in-group schedules.
First observe that the number of rounds is equal to the number of pairs of ambassadors divided by the number of meetings per round; this is n(n-1)/2 divided by n/2 or n-1 rounds.
Step 1 takes zero time. Step 2 takes Theta(n2) time. Step 3 takes 2T(n/2) time. Step 4 takes Theta(n) time per round for n-1-n/2 = n/2-1 rounds, costing Theta(n2) time. So the recurrence for the total running time is
T(n) = 2T(n/2) + Theta(n2) = Theta(n2) by the MasterTheorem.
2. Insistent select
Let p be the probability that neither pile has greater than n/2. Because the sizes of the two piles must sum to n-1, this can occur only if one pile has n/2-1 elements and the other n/2 when n is even (2 out of n cases), or when both have size (n-1)/2 when n is odd (one out of n cases). So p is either 2/n or 1/n. For either value of p, we can compute the expected number of times we split the array using the equation S(n) = 1 + (1-p) S(n), since we always do it once and then have to start over with probability (1-p). Solving this equation for S(n) gives S(n) = 1/p = Theta(n). So T(n) = Theta(n2) + T(n/2) = Theta(n2).
- Now we want the probability that neither pile gets more than (3/4)n of the elements. This event occurs when the pivot lies between index n/4 (give or take a small additive constant) and index (3/4)n, or approximately one half of the time. By the previous analysis we have S(n) = 1/p = 2 = Theta(1), and so T(n) = Theta(n) + T((3/4)n) = Theta(n).
If c is any constant less than 1/2, then (n-1)/2 = n/2 - 1/2 > cn for sufficiently large n. But the split will always leave a pile with (n-1)/2 or more elements. So for sufficiently large n it will not terminate in this case. (We have already seen that the algorithm terminates when c = 1/2, so this result is tight.)