In a tennis tournament, there are n players, where n = 2k for some positive integer k. In the first round, each player competes against another player. Only the winners advance to the second round. In the second round, each remaining player competes against another player, and only the winners advance to the third round. This process continues until a single winner is determined. Let f(n) represent the total number of matches played in the tournament. Use a diagram like the one shown below (called a bracket) to help you answer the following questions.

1. (a) In a tennis tournament, there are n players, where n2for some positive integer k. In the first round, each player competes against another player. Only the winners advance to the second round. In the second round, each remaining player competes against another player, and only the winners advance to the third round. This process continues until a single winner is determined. Let f(n) represent the total number of matches played in the tournament. Use a diagram like the one shown below (called a bracket) to help you answer the following questions. 16 Team Single Fiminatioin Winner PrintY i. Briefly explain in words why f(n) satisfies the recurrence f(n)2f(n/2), f(1)0. What is the Big O description of f (n) given by the Master Theorem, using this recurrence? ii. Briefly explain in words why f (n) also satisfies the recurrence f(n) = f(n/2) + n/2, f(1) = 0. What is the Big O description of f (n) given by the Master Theorem, using this recurrence? (b) Suppose an algorithm solves problems by dividing them into five subproblems of half the size recursively solving each subproblem, and then combining the solutions in O(n) time. What is the Big-O class of its runtime? (c) Suppose an algorithm solves problems by dividing them into four subproblems of one third the size, recursively solving each subproblem, and then combining the solutions in O(n) time. What is the Big-O class of its runtime