1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.