Word problems on Master Theorem

Divide-and-Conquer Algorithms and Recurrence Relations

The management of High Balcony Hotel is running a promotion campaign. As the ?nal event of the campaign, the management is awarding a prize to one of n guests. The winner is chosen as follows. First, all n candidates gather in one of the dining rooms, and they all sit down so that exactly four persons occupy each table. The four occupants of each table then play a short lottery game, in which exactly one of these four persons wins. All winners then proceed to the next dining room, sit down again in groups of four, and each group selects one winner by playing a lottery game; all the winners then move into a new dining room. This procedure continues until only one winner is left, who receives the prize. (a) Let r(n) be the total number of dining rooms visited while selecting the winner from n guests. Write a recurrence relation that governs the asymptotic order of r(n). (b) Let g(n) be the total number of lottery games played while selecting the winner from n guests. Write a recurrence relation that governs the asymptotic order of g(n). (c) Find an asymptotic estimate for r(n). Show your work. (d) Find an asymptotic estimate for g(n). Show your work.