3
$\begingroup$

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)$ time. 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.

$\endgroup$
  • 3
    $\begingroup$ 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? $\endgroup$ – Yuval Filmus Feb 21 '18 at 18:39
  • 2
    $\begingroup$ 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. $\endgroup$ – D.W. Feb 21 '18 at 18:55
  • $\begingroup$ @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. $\endgroup$ – einpoklum - reinstate Monica Feb 21 '18 at 19:12
  • $\begingroup$ 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 .) $\endgroup$ – Apass.Jack Jun 24 at 19:16
  • 1
    $\begingroup$ @einpoklum "The default value 0 for all elements is part of the particular RAM model" (that I defined). If you do not think that is a valid computation model at all, it is your choice. Note that for example all cells of a Turing machine are assumed to contain the blank symbol. That is (part of the reason) why I believe it is reasonable to include that in my computation model. By the way, we do not "finally read the entire array" since we will add an element $a_i$ to the set of distinct elements only when $arr[a_i]$ is changed from 0 to 1. So at the end, we will just return that set. $\endgroup$ – Apass.Jack Jun 25 at 5:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.