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<\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 "buckets" $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.

  • $\begingroup$ So, I have to accept this, because that's how I asked the question, but this uses a lot of extra space. I had assumed since we weren't sorting nor hashing, there won't be much sense in using extra space, but you proved me wrong. So +1 and maybe I'll ask a followup. $\endgroup$ – einpoklum Sep 14 '20 at 13:09
  • $\begingroup$ @einpoklum I believe you can make all of this with $O(1/\alpha)$ extra space (but I didn't think through it very hard and might be mistaken). If you need constant extra space then I'm out of ideas :) $\endgroup$ – Tassle Sep 14 '20 at 13:20
  • $\begingroup$ That's under the assumption that I can reorder my data, which actually I can't. I don't mind $O(1/\alpha)$ space, but the input must stay untouched. Anyway, it'll be a different question. $\endgroup$ – einpoklum Sep 14 '20 at 13:24

Very partial answer: At least for $\alpha > 0.5$, yes.

  1. $\text{candidate}$ <- (null value), $\text{count}$ <- 0

  2. For each element $x$ in the array

    1. If $x = \text{candidate}$ then

      1. increment $\text{count}$
    2. else

      1. If $\text{count} = 0$

        1. $\text{candidate} \leftarrow x$, $\text{count} \leftarrow 1$
      2. else

        1. decrement $\text{count}$

The candidate remaining at the end of the array is the majority element. A potential-function argument can show this to be the case (I was taught this in a teaser for an online algorithms class).

This can be extended to $\alpha = 0.5$ by first finding two distinct elements of the array, then running the above on the array without one of them, then on the array without the other, then finally checking the frequency of the values you get from those two runs.

But - such a trick will probably not work for lower $alpha$ values.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.