Suppose we have an even number of objects, n$,$ and are only allowed to test for equality. That is$,$ we can

select two of the objects and tell, in unit time, if they are the same or not. Design an algorithm to test if

the set of n objects has any object which is a strictly majority element, that is strictly more than n$/2$ of

the objects are the same. If so$,$ return the majority element.

Try to design an O$($n log n$)$ algorithm, using a divide and conquer approach. Justify why your algo$-$

rithm is correct. Also justify the upper bound on the run$-$time of your algorithm.