About the complexity of deciding whether no two elements of a collection are the same
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.