The theoretical upper bounds for duplicate detection in a set of objects? I recently had a lengthy exchange with someone about the most efficient way to remove duplicates from a collection.  The debate was mostly centered around the specific behavior of C# collections, such as HashSet(T) and HashTable(T).

I think we agreed on the fundamentals, but where we couldn’t come to an agreement was what the constraints are with very large sets.  

He told me to investigate the theoretical (ie absolute) bounds for duplicate detection in a set of objects… But I don’t really know what that means.  I don’t think there’s an absolute bounds if you can break up the problem sufficiently.  

There may be a point at which you can no longer use a HashSet / HashTable in .NET because I know that if you are using the framework au-naturale you are constrained by the number of unique values an Int32 can express and the amount of memory you have available.

But the issue of storage and memory issue comes much sooner than the number of unique values, which is typically what the theoretical is concerned with... For example if the data type is integers for the initial set you're removing duplicates from, you run out of memory before the numeric range of the integer type becomes a problem:


If I am storing integers, I know that there are 2^32 possible integer values.
To store an integer, I need 32 bits of space, so the total memory required to store all distinct integers is 2^32*4 bytes, which is 17.18 gigabytes.
The amount of memory that can be addressed in a 32 bit architecture is 2^32 bytes or approximately 4.295 gigabytes


Even if I’m not using a hashset, I can see that in order to store that many values, I would need at least four times the amount of memory addressable by the architecture for the initial collection.  And that's not even factoring in the duplicates we're seeking to remove.

I would also need memory proportional to the size of the initial set for the hash set implementation and hash set value storage… So the use of a hashset quickly becomes unfeasible when you exceed millions of unique values.

I’ve already asserted to him that if you had a large digit such as a long, and you had billions of values, you would not use a hashset.  Hypothetically I might store the data in distributed nodes that are pre-sorted by the unique field, or implement a distributed mapreduce sort implementation, followed by a mapreduce duplicate value removal algorithm.

He didn’t acknowledge the feasibility of the sort/remove duplicates approach though… And was quite insistent that there is an upper bound for duplicate detection.

Could anyone tell me what the ‘absolute’ bounds for duplicate detection for a set of objects is?  Or what he was was referring to by it?
I think you're asking about the "Element Distinctness Problem."

Assuming you're talking about time complexity (number of comparison operations) rather than space complexity, "lower bound" instead of "upper bound," and that you can't hash elements of your multiset (which gives you $O(n)$ expected time), then the best you can do is $\Theta(n \log n)$.