1. Map coloring

1. We have to test each adjacent pair to see if colors of the two countries are the same; each such test takes Theta(1) time, so the total is Theta(m).

2. Since each country can have three different colors, there are 3ⁿ possible colorings, for a total cost of Theta(3ⁿm).

3. Now each country after the first has at most two possible colorings (since one is excluded by an earlier neighbor). So there are at most 2^n-1 colorings, which gives a cost of O(2^n-1m) = O(2ⁿm). This is much better than Theta(3ⁿm), since it's easy to show that it's o(3ⁿm).

   • This upper bound is in fact the best we can do without further optimizations: Consider a map in which every country is adjacent to every other. With n > 3, this clearly can't be colored with only three colors. But the algorithm will try 2^n-1 colorings anyway, because it has no mechanism to exclude bad colorings except the test at the end.

2. Suspicion

1. It's not clear that we can do much better than BruteForce for this. The simplest BruteForce approach generates all n^k possible conspiracies (or, strictly speaking, all n choose k, but this is Theta(n^k)) and tests each one by probing each of k(k-1)/2 links in Theta(k²) = Theta(1) time, for a total cost of Theta(n^k) in the worst case.

2. The above algorithm can be trivially modified to find all conspiracies; the only additional cost is the cost of generating the output, but this is again bounded by Theta(n^k).

Faster algorithms are welcome! Correct algorithms that run in time bounded by a polynomial whose exponent does not depend on k qualify for substantial extra credit.