Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

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(n²) 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(n²) time. So the recurrence for the total running time is

T(n) = 2T(n/2) + Theta(n²) = Theta(n²) 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(n²) + T(n/2) = Theta(n²).
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.)