44 views

You have an array $A$ with $n$ objects, some of which are identical. You can check if two objects are equal but you cannot compare them in any other way—i.e. you can check A[i] == A[j] and A[i] != A[j], but comparisons such as $A[i] < A[j]$ are not meaningful. (Imagine that the objects are JPEG images.) The array A is said to have a majority element if strictly more than half of its elements are equal to each other. Use divide and conquer to come up with an $O(n \log n)$ algorithm to determine if $A$ has a majority element.