# Element distinctness in O(n) time?

We all know that element distinctness in the comparison based model cannot be done in $o(n\log n)$ time. However, on a word-RAM, one can possibly achieve better.

Of course, if one assumes the existence of a perfect hash function that can be computed in linear time, we get a linear time algorithm for element distinctness: just keep hashing the numbers one by one and return 1 if there is a collision.

However, there are two issues: 1) most constructions of perfect hash functions that I could find used randomness and 2) I cannot find a discussion of the pre-processing time anywhere, i.e., the time required to decide what hash function one is going to use based on the input set of numbers.

Fredman et al.'s "Storing a sparse table with $O(1)$ worst case access time" does resolve the first issue by providing a hash function with $O(1)$ access time in the worst case, but says nothing about the second issue.

So to sum up, here's what I want:

Design an algorithm that given a set $S$ of $n$ numbers (each number being $w$ bits long) on a word-RAM with word length $w$, finds a hash function $h:S\rightarrow \{1, \ldots , m\}$ in $O(n)$ time, where $m = O(n)$. The function $h$ should have the property that for any $j \in \{1, \ldots , m\}$, the number of elements of $S$ that map to $j$ is a constant and computing $h(i)$ should take $O(1)$ time in a "reasonable" word-RAM model, i.e., the model should not allow "exotic" functions on words to be evaluated in $O(1)$ time.

I will also like to know if there are algorithms to solve element distinctness on the word-RAM that do not use hash functions at all.

• Re: "I will also like to know if there are algorithms to solve element distinctness on the word-RAM that do not use hash functions at all." — as long as you only want $o(n\log n)$ and not linear, there is lots of work on sorting on the word RAM (see en.wikipedia.org/wiki/Integer_sorting). Some of these algorithms use hashing but others do not. – David Eppstein Nov 15 '12 at 7:59
• Are approximate solutions allowed? – A T Jan 27 '13 at 14:31
• (I think that) Your thinking process is skipping one step: 1. You postulate that the best complexity in the comparison model is $\Theta(n\log n)$ 2. You ask how this can be improved in the RAM model 3. You directly ask for a solution in $O(n)$ time in the RAM model. Rather, you should be studying the solutions in $o(n\log n)$ in the RAM model and see if you can improve them? – Jeremy Mar 24 '13 at 17:58
• Is Radix sort too slow for you? – Thomas Mueller Dec 23 '15 at 14:43

Element distinctness can be solved deterministically in the RAM model in time within $O(n\log\log n)\subset o(n\log n)$ time:
Sort in time within $O(n\log\log n)$ your $n$ numbers of $w$ bits using the sorting algorithm described by Han in STOC 2002 ("Deterministic sorting in $O(n\log\log n)$ time and linear space"), then scan in linear time for collisions.