Finding the most frequent element assuming $\Theta(n)$ frequency
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.