1
$\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). Denote $\text{supp}(s) = \left\{ x \in \mathbb{N} \;|\; x \in s \right\}$, the support set for $s$.

We are interested in obtaining a supporting sequence $s'$ of elements such that $\text{supp}(s) = \text{supp}(s')$; in other words, we want a sequence of elements, in any order and possibly with repetitions, with appearances of all of elements appearing in $s$ (and no others).

The minimum such sequence is any ordering of the actual support set for $s$. But - we don't need the minimum itself. In fact, we are given a size bound $m$, and must produce an $s'$ with $|s'| \leq m$.

What algorithmic approach would you suggest for producing $s'$, which would have meaningfully better than just obtaining the exact support set - in terms of worst-case time complexity?

This question is related to this one.

Notes:

  • The algorithm is not limited to just comparisons (so hashing is on the table if you like).
  • Obviously, the complexity cannot be any better than $\Theta(n)$, since you have to actually read all the input; and it can't be worse than $\Theta(n \log(n))$, with which complexity you can just obtain the exact support.
  • Constant-factor improvements are significant, e.g. fewer reads of each element, even if the $O(\cdot)$ or $\Theta(\cdot)$ class might be same. I'm hoping for something that depends on $m$ or $m - |s'|$ obviously.
$\endgroup$
  • $\begingroup$ Better in what respect? Are you trying to minimize worst-case running time? What's your model of computation? Do you require a deterministic algorithm? Do you require an algorithm that uses only comparisons? Do you need a streaming/online algorithm? The running time of different algorithms might depend in a delicate way on these assumptions. What counts as significant? You're not going to be able to get more than a $O(\log n)$-factor speedup. $\endgroup$ – D.W. Nov 21 '19 at 17:39
  • $\begingroup$ @D.W.: Sorry, I should have added more details before submitting the question. See edit. $\endgroup$ – einpoklum Nov 21 '19 at 19:25
  • 1
    $\begingroup$ I still wonder if hashing might be the best solution. I see that in your previous question you rejected it because it is not deterministic, but given that you mention constant-factor improvements, I wonder whether hashing might actually be the best solution. If you use 2-universal hashing, not only is the expected running time $\Theta(n)$, but we can also prove that there is a small constant $c$ such that there is only an exponentially small probability that the running time exceeds $c\cdot n$. I don't think it makes engineering sense to worry about exponentially small probabilities; [..] $\endgroup$ – D.W. Nov 21 '19 at 20:34
  • $\begingroup$ they are smaller than the probability that a cosmic ray hits your microprocessor and causes it to produce the wrong output or enter an infinite loop. If we're willing to accept the risk of cosmic-ray-induced faults (which most people seem to be), then it seems like we also ought to be willing to accept the risk of an exponentially small chance of getting a poor random seed that causes our algorithm to take longer (or produce the wrong output). [...] $\endgroup$ – D.W. Nov 21 '19 at 20:35
  • $\begingroup$ From a theoretical perspective the difference between deterministic vs randomized algorithms is interesting, but if we adopt that theoretical perspective, constant factors are normally irrelevant. So I'm struggling to find a context that would lead to the stated requirements and that also makes hashing unacceptable. $\endgroup$ – D.W. Nov 21 '19 at 20:36

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.