A question about recursive algorithm design.
Let A be a set of n items. The only operation available to you is "compare(x,y)", which returns "ture" if x = y and "false" otherwise. An item is said to be a majority item if it occurs at least n/2 + 1 times. Write an O(n) worst-case time (recursive) algorithm that decides if a majority item exists, and if so, identifies it. Explain why it takes O(n) time.