Single-elimination tournaments are notorious for their scheduling difficulties. Imagine that you are organizing a tournament for n basketball teams (you may assume that n = 2i for some integer i). We will further simplify things by assuming that each game takes less than an hour, and that each team can be scheduled for a game every hour if necessary. (Note that everything said here about basketball courts is also true about processors in a parallel algorithm to solve the maximum-finding problem).
(a) How many basketball courts do we need to insure that every team can play whenever we want to minimize the total tournament time?
(b) How long will the tournament be in this case?
(c) What is the total number of "court-hours" available? How many total hours are courts being used? How many total court-hours are unused?
(d) Modify the algorithm in such a way as to reduce the total number of courts needed, by perhaps not letting every team play whenever possible. This will increase the total hours of the tournament, but try to keep the increase as low as possible. For your new algorithm, how long is the tournament, how many courts are needed, how many total court-hours are available, how many court-hours are used, and how many unused?