Recently, Hooli Inc, a large international company, had an election to choose their CEO for the next 5-year period. A candidate can be selected as the new CEO, only if they gather a majority vote, meaning that from the n votes submitted by shareholders, they get more than n=2 votes. Hooli claimed that in the recent vote no candidate got a majority, so the current CEO will be hired for the time being. A freedom of information request was made by a news agency to Hooli to disclose the votes for the election. Hooli said that, due to privacy concerns, they cannot disclose the votes because the reputation of the candidates with very few votes will be damaged. Instead, they have been able to quickly set up an API for the news agency. Every query to the API is of the form QueryAPI(i, j), where i and j are two integers in the range [1...n] (the number of votes, n is known publicly). The query returns True if the ith vote and the jth vote were cast for the same candidate, and False otherwise.

As an example of how to access the API, we can run QueryAPI(1, k) n - 1 times with k = 2, ..., n to count how many of the votes are given to the same candidate as the first vote. Hooli is charging a ridiculous amount of money for every query made to the API. We are interested in checking whether there is a majority in the n votes or not, and we want to use the least number of queries.

Part 1) Using the following claim [ "Suppose X has a majority in list S, if we partition S into two lists with roughly n/2 votes in each, then X has a majority in either S_left or S_right "], describe a divide-and-conquer algorithm to check whether or not some candidate has a majority, using O(nlogn) queries to the API.

Part 2) Write the recurrence relation for the number of API calls, Q(n), of your algorithm in part 1. Give a big-O bound on the number of API calls, Q(n). (Hopefully it is O(nlogn))