# frequency of elements in array in $\mathcal{O}(n) ?$

I have an array of 64-bit integers of length $$n$$ and I want to find the frequency of each element in $$\mathcal{O}(n)$$? is that possible?

my idea was to use a hashmap but it seems to me that the adversary would always be able to find a pathological case.

• Yes, you can use HashMap. adversary would always be able to find a pathological case: you can use your own hash function: $h(x) = p \cdot x \pmod {m}$, where $p$ and $m$ are (large) prime numbers randomly selected at the beginning of the program. While adversarial inputs exist (e.g. $0$, $m$, $2m$, ...), the adversary doesn't know them, since they don't know $p$ and $m$.
– user114966
Sep 4, 2020 at 23:35
• Since they are integers of fixed length, you can sort them in $O(n)$ and then count their repetitions in one pass.
– plop
Sep 5, 2020 at 1:51
• Use radix sort with an "alphabet" of size 256, say. Sep 5, 2020 at 5:52
• Is there a limit on the $n$? Sep 5, 2020 at 7:11
• Since the integers are all upper bounded by an absolute constant the "counting" part of counting sort already solves the problem in $O(n)$ time. Sep 5, 2020 at 12:50