Suppose you have an unsorted array A[1..n] of elements. You can only do equality tests on the elements (e.g. they are large GIFs). In particular this means that you cannot sort the array. You want to find (if it exists) a majority element, i.e., an element that appears more than half the time. For example in [a, b, a] the majority element is a, but [a, b, c] and [a, a, b, c] have no majority element. Consider the following approach to finding a majority elememt: Recursively find the majority element y in the first half of the array and the majority element z in the second half of the array...

a) prove that if x is a majority element in A then it is a majority element in the first half of the array or the second half of the array (or both).

b) Using part (a) give a divide-and-conquer algorithm that runs in time Detailed pseudocode is required. Be sure to argue correctness and analyze the run time.

O(n log n O(n log n