Analysis of prisoners algorithm

Problem 69 presents a problem of grouping \(n\) prisoners into 2 cells, where there are \(m\) pairs of prisoners that don't get along and should not be grouped together.

We saw that a clever deterministic algorithm guarantees that the number of pairs of enemies that are not in the same cell together is at least \(\frac{m}{2}\).

Here is a rather un-clever randomized solution: For each of the \(n\) prisoners, flip a coin to determine which cell they go into, randomly. So each prisoner ends up in one cell with probability \(\frac{1}{2}\), or the other cell with probability \(\frac{1}{2}\).

Complete the end of Problem 69 for this algorithm:

2. Explain why the number of enemies within either cell will be at most \(m/2\), on average, after running your algorithm.
3. Analyze the worst-case big-O running time of your algorithm.

Hint: for (2), consider each of the \(m\) enemy pairs individually. What is the probability that that pair is in the same cell or in two different cells?