Why is the lower bound of element uniqueness in $\Omega(n\log n)$?

Question

I wish to discuss the element uniqueness problem. First let's define the problem:

Definition from wikipedia:

In computational complexity theory, the element distinctness problem or element uniqueness problem is the problem of determining whether all the elements of a list are distinct.

i am aware that this question has been asked before, however, I am confused about what lower bound actually means.

Let's say we are given an arbitrary array of integers. We could simply use hashing to check for element uniqueness. Hashing works in amortized $O(1)$ time. Hence, shouldn't the lower bound of element uniqueness be $\Omega(n)$?

Am I understanding lower bound wrongly? Does lower bound mean an asymptotic lower bound for general cases (i.e. we could have arrays of strings as well) or does it apply to all cases?

Answer 1

We assume the comparison model in the lower bound of the element uniqueness problem. That is, the key operations are to compare elements. In particular, hashing is not allowed.

Answer 2

I see at least two objections to your linear-time solution for the element uniqueness problem. First, the algorithm you propose doesn't work, because hashing works for most datasets and most hashes, but by the pigeon hole principle, not always. If an adversary knows the hash you use, she can give you a list of items that all hash into the same bucket. (She simply draws $n$ items from her favourite bucket. These exist, if the hash sufficiently reduces the length of the item, namely by at least $\log(n)$ bits).

Second, the assumption that hashing is in $O(1)$ time, works in a computational model where you can manipulate these items in constant time, but this isn't necessarily realistic. Suppose that all of $n$ elements are unique. Then each element is described by at least $\log(n)$ bits, so the length of these registers grows with $n$, so realistically you can't manipulate registers in constant time. Then hashing takes $\Omega(\log(n))$ time, and hashing $n$ elements takes $\Omega(n\log(n))$ time.

The same objection holds against the model where comparison is $O(1)$; here sorting takes $O(n\log(n)^2)$ real-world steps, where $n$ is the number of items, if you use QuickSort and use a black-box sorting algorithm. In a sense, this is a strange model; items can be compared in $O(1)$ time, but they can't be hashed in $O(1)$ time.

Answer 3

If you use a hash table, I will examine your hash function, and give you an array of values that all have the same hash value. Your hashing will take quadratic time. Actually, if you have say an excellent 64 bit hash function, and the number of values is not limited (much bigger than $2^{64}$ items), then most hash tables will run in $\Theta(n^2)$ with a tiny, tiny constant. The quadratic behaviour only shows itself if n is much larger than $2^{64}$.