Finding the most frequent element assuming $\Theta(n)$ frequency 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?
Here is an algorithm for all $0&lt;\alpha\leq 1$. I'm assuming your data can be ordered and that comparing two elements is done in constant time.
Run a few levels of the quick-sort recursion (choosing the pivot optimally in linear time with the Median of Medians algorithm) until you have partitioned the elements into &quot;buckets&quot; $B_1,\ldots, B_m$ each of size $\frac{\alpha n}{4} \leq |B_i| \leq \frac{\alpha n}{2}$, where all elements in $B_i$ are smaller or equal to all elements in $B_{i+1}$.
This will take $O(n\log(1/\alpha))$ time.
Now notice that because the relative majority element $e$ is present at least $\alpha n$ times and each bucket has at most $\frac{\alpha n}{2}$ elements, the majority element needs to fill at least one of the buckets completely. Thus $e$ is also  the first element in some bucket.
Notice also that there are at most $4/\alpha$ buckets as each bucket contains at least $\frac{\alpha n}{4}$ elements. Thus you can pick the first element in each bucket, and choose the element with maximum frequency among those in $O(n/\alpha)$ time.
Thus, you can find that relative majority element $e$ in $O(n\log(1/\alpha) + n/\alpha) = O(n/\alpha)$ time.