6
$\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.

Improve this question
$\endgroup$
14
  • 4
    $\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, 2018 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, 2018 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
    Feb 21, 2018 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$
    – John L.
    Jun 24, 2019 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$
    – John L.
    Jun 25, 2019 at 5:37

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.