Comparison-based lower-bound for finding duplicates in an array of $n$ numbers

Question

Decision Problem: Given $n$ real numbers, give an algorithm that outputs "1" iff there are at least two numbers that are identical and outputs "0" otherwise. (Assume that comparison between any two numbers works in $O(1)$-time).

The problem is obviously solvable in $O(n\log n)$-time via augmenting mergesort, and when we limit the numbers to integers or bitstrings, we might be able to use hashing to improve the runtime.

However, an acquaintance told me that there is an $\Omega(n\log n)$ lower bound to this problem on the comparison model, meaning that this problem is as hard as sorting. Is he correct? If so, give a proof.

Answer 1

Your problem is known as element distinctness. You can find $\Omega(n \log n)$ lower bounds for several computation models in the answers to a question on cstheory. The lower bound for the comparison model is particularly simple.