# What is the deterministic time complexity of obtaining the set of distinct elements?

Consider a sequence $s$ of $n$ integers (let's ignore the specifics of their representation and just suppose we have can read, write and compare them in O(1) time with arbitrary positions). What's known about the worst-case time complexity of producing a sequence of all distinct elements in $s$, in any order?

By randomized hashing, one can do this in expected $O(n)$. On the upper bound side, one may sort the elements, then produce the output in a single pass by only copying elements which differ from their predecessors to the output - for a total time of $O(n \log(n))$.

But can one do better than $O(n \log(n) )$ deterministically?

Note: This is sort-of a "remove duplicates" problem, but since the order is not preserved I'm not sure it should be called that.

• There is an $\Omega(n\log n)$ lower bound on element distinctness (finding out whether all elements are distinct) in the comparison model. Does this answer your question? – Yuval Filmus Feb 21 '18 at 18:39
• I don't think we can ignore the specifics of the representation and computational model because sorting is known to be somewhat delicate and dependent on that -- for instance, Wikipedia seems to suggest it is known how to sort in $O(n \log n / \log \log n)$ time in some computational models, and even in $O(n (\log \log n)^2)$ time. So at least in some computational models that is a "yes one can do better" answer to your question. – D.W. Feb 21 '18 at 18:55
• @YuvalFilmus: Comparisons model, eh? I think perhaps not, since the hashing strategy, while non-deterministic, is not in the comparisons model. But +1 on that comment. – einpoklum Feb 21 '18 at 19:12