# 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 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
• When we have unbounded memory, $h(m)=m$ is a realizable hash function without conflict. The time-complexity is deterministic $O(n)$. (The space-complexity is $O(\max(a_i))$, where $\max(a_i)$ is the maximum of given numbers. Every time a larger number is read, we double the working space .) – Apass.Jack Jun 24 at 19:16
• @Apass.Jack: The case of $max\{s\} - min\{s\} = O(n)$ is too narrow for me, and in the general case your suggestion doesn't seem to help. – einpoklum Jun 24 at 20:51