Suppose you are writing a simulator for a single-elimination sports tournament (

Question

Suppose you are writing a simulator for a single-elimination sports tournament (like in NCAA Division-1 basketball). There are n teams at the beginning of the tournament and in each round of the tournament teams are paired up and the games for each pair are simulated. Winners progress to the next round and losers are sent home. This continues until a grand champion team is the final winner. Suppose your simulator takes O(log n) time to process each game. How much time does your simulator take in total?

Explanation / Answer

Since this is a single elimination game, each round will consist of n games, then n/2 games, then n/4 games. Since each game takes O(log n) time, the first round will take n log n time, then n(log n/2)/2 time, then n(log n/4)/4 time, etc. So total time is the sum of n(log n/i)/i, with i going from 1 to log_2 n. This just ends up being roughly (n log n)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.