About the complexity of deciding whether no two elements of a collection are the same

Given a collection of $n$ numbers, $S$, the question is to decide whether all the elements of $S$ are distinct from each other. If they are distinct from each other (no two of them are the same), print "Yes". Otherwise print "No".

I know the worst case time complexity of this question is $\Theta \left ( n\log n \right )$. Of course it is based on comparison among elements. But I can't figure out how to prove this. Perhaps using the decision tree?

I think there is something wrong with your claim that the complexity is $\Theta(n \lg n)$. At least, it is not quite that simple. You don't say where you got that claim from, but I don't think it is accurate, at least in general.

The problem can be solved faster, in some machine models. For instance, there are sorting algorithms with running time faster than $\Theta(n \lg n)$, in some machine models, and there are other ways to solve this problem -- e.g., using a hash table using a 2-universal hash function should yield a solution whose expected running time is $\Theta(n)$, under a reasonable model of computation.

What is your machine model? A RAM machine? What notion of complexity are you OK with? Worst-case running time of a deterministic algorithm? Are you OK with a randomized algorithm? The complexity of the problem will depend upon these fine details.

StackExchange Computer Science Q#18807, answer score: 4