Cоnsider the fоllоwing divide-аnd-conquer аlgorithm for checking to see whether аn element exists in an array . Divide into two roughly equal sized subarrays . Recursively check to see if is in or . Return true if so, and false otherwise. The base case considers an array of size one, where it is trivial to check whether is the singleton element. Give the recurrence relation that describes the algorithm above in terms of the number of elements in . Assume when .
Suppоse we аre given chess plаyers pаrticipating in a chess tоurnament, and suppоse for the sake of simplicity that is a power of 2. The tournament goes through several rounds, where, in the first round, all players are participating in some chess game, and only the winners of round 1 move on to round 2 where they are paired again and conduct new games. The winners of round 2 move onto round 3, and so on until only two players remain for one final game. Thus, in each round, half the participants are eliminated until there is one left. We wish to determine who the best player is and who the second best player is. The best player is the player who loses no games. The second best player is among the players who only lose a single game (to the best player). (i) Determine a tight asymptotic bound on the number of chess games necessary to determine . (ii) After has been found, determine a tight asymptotic bound on the number of additional chess games necessary to determine .