3. A set S of n elements has a majority element if more than half of the elements are the same. The only operation you can do with two elements is to tell if they are the same or not. Here is (most of) an algorithm to test if set S has a majority element, and to identify it if there is one. Majority (S, n) Step a: If n is even, pair up the elements of S arbitrarily, forming n/2 pairs. If S is odd, then ignore one element, keeping it in S and ements. arbitrarily pair up the other el Step b: Look at each pair. If the two elements are the same, remove one from S. If they are different, remove both of them from Step c. Call the algorithm again (i.e., recurse) with the updated S. That is, call Majority (S,m), where m is the number of ele- ments in the updated S The algorithm description lacks a base case. State a base case for this algorithm Is the algorithm correct? That is, will it always correctly determine if there is a majority element, and identify it if there is one? Hint: Show that if there is a majority element in S before the execution of Step b, then there will be a majority element in S after the execution of Step b In worst case, how many comparisons does this algorithm do? Set up and solve a recurrence relation for this. Hint: Show that after each execution of Step b, the number of elements left is at most a half, plus one, of the number of ele d nents before Step b was execute