Finding the most frequent element, given that it’s Theta(n)-frequent?


We know [Ben-Or 1983] that deciding whether all elements in an array are distinct requires $ \Theta(n \log(n))$ time; and this problem reduces to finding the most frequent element, so it takes $ \Theta(n \log(n))$ time to find the most frequent element (assuming the domain of the array elements is not small).

But what happens when you know that there’s an element with frequency at least $ \alpha \cdot n$ ? Can you then decide the problem, or determine what the element is, in linear time (in $ n$ , not necessarily in $ 1/\alpha$ ) and deterministically?