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


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.