A large online social networking company has recently discovered that it may have a problem with a number of accounts that are spreading false information through the site. The company has a collection of n accounts that they have been monitoring over the last several months, suspecting them of being used for such activity. Each account has the following data associated with it: a user id, some possibly fraudulent information (such as the name, etc.), and a unique encrypted number generated by the site when the account was created. A user can have more than one account on the site. The company will not disclose the identity of the account holders directly without a subpoena, but will tell if two accounts belong to the same user. Required:
a. The government agency’s question is the following: among the collection of n accounts, is there a set of more than n/2 of them that are all associated with the same user? Assume that the only feasible operation the government investigators can do with the accounts is to choose two of them and ask the company if they belong to the same user (and the company people get more and more reluctant to answer each time).
b. Show how to decide the answer to the agency’s question with only O(nlog n) requests to the social networking company