0
$\begingroup$

What are some ways of commutatively combining a pair of lists to produce a list comprised of elements from the pair of inputs, with no duplicates, with time complexity better than $O(n \log(n))$? Suppose we have the following inputs

$a = [5, 1, 6, 8]$

$b = [8, 4, 5, 2, 10]$

We would like to commutatively combine $a$ and $b$ to produce a list with no duplicate elements (i.e. if F denotes a function that satisfies the aforementioned criteria, then $\forall x, y \quad F(x, y) = F(y, x)$). One possible valid output is $c = [1, 2, 4, 5, 6, 8, 10]$ - since the output doesn't have to be sorted, any permutation of $c$ is just as valid (although consistency would be nice). The most obvious naïve algorithm concatenates the two lists, then removes duplicates, then sorts the result in $O(n \log(n))$ time.

Is there a commonly used name for this kind of problem, and where can I find literature about it?

$\endgroup$
9
  • 2
    $\begingroup$ Are you asking for a way to compute the union of two lists? $\endgroup$ Commented Aug 16, 2011 at 9:12
  • 3
    $\begingroup$ I don't think this is a research level question. $\endgroup$ Commented Aug 16, 2011 at 10:21
  • 4
    $\begingroup$ Even ignoring the commutativity requirement, the problem of eliminating duplicate elements is called duplicate elimination, and has a lower bound of n log n in the comparison model. More precisely, it's $n \log n - \sum_i n_i \log n_i$ where $n_i$ is the multiplicity of the $i^{\text{th}}$ element. See Munro, I., Spira, P.: Sorting and searching in multisets. SIAM Journal on Computing 5 (1976) 1-8 $\endgroup$ Commented Aug 16, 2011 at 11:46
  • 3
    $\begingroup$ If the input sequences are possibly not sorted, then I don't see what's the point of saying you have two sequences. $\endgroup$ Commented Aug 16, 2011 at 13:35
  • 1
    $\begingroup$ To the asker: Please edit the question to clarify whether the input sequences are already sorted or not. −1 for this ambiguity. $\endgroup$ Commented Aug 16, 2011 at 14:51

3 Answers 3

4
$\begingroup$

Yes and no.

Set interaction is one of the problems specifically studied in Ben-Or's seminal paper on lower bounds for algebraic decision and computation trees. The problem is formally defined as follows: Given two sets of n numbers, is their intersection empty? Equivelently, does their union have exactly 2n elements? Ben-or proves a lower bound of Ω(n log n) for this problem. If the sets have diffent sizes n>m, the lower bound becomes Ω(n log m), but this only beats the naive O(n log n) bound if m is subpolynomial in n.

On the other hand, if your list elements are integers, you can solve the problem in o(n log n) time using fast integer-RAM sorting algorithms. For reasonable word sizes, I believe the fastest integer sorting algorithm runs in $O(n \sqrt{\log \log n})$ expected time [Han and Thorup, FOCS 2002].

$\endgroup$
1
  • $\begingroup$ I ignored the phrase "average case" in the title, because it didn't appear in the question itself. $\endgroup$
    – Jeffε
    Commented Aug 20, 2011 at 22:41
0
$\begingroup$

I'm not sure I understand the question completely. Do you want an algorithm that, given two sorted sequences each containing no duplicates, outputs a new sorted sequence containing every item in either of the input sequences and also no duplicates?

If so, you can represent the larger sequence as a special type of tree (a finger tree), then merge the sequences in $O(i \lg (k/i))$ merges, where $i$ is the size of the smaller sequence and $k$ is the size of the larger sequence. I think this is asymptotically optimal in the pointer machine model.

$\endgroup$
6
  • 2
    $\begingroup$ I don't think the OP is assuming the original sequences are sorted. $\endgroup$ Commented Aug 16, 2011 at 11:41
  • 2
    $\begingroup$ If the lists are sorted, then you just merge them (no need for fancy trees). $\endgroup$ Commented Aug 16, 2011 at 13:34
  • $\begingroup$ @Radu GRIGore: Yes, but then you may make O(k) comparisons, which is not so great if i is small. $\endgroup$
    – jbapple
    Commented Aug 16, 2011 at 14:40
  • 1
    $\begingroup$ Can you build the finger tree faster than O(k)? $\endgroup$ Commented Aug 16, 2011 at 14:59
  • $\begingroup$ @Radu GRIGore - Not really, or at least not helpfully in this case, but the survey I linked from Brodal explains why this merge time may be useful in any case See sections 11.5.2 and 11.5.4. $\endgroup$
    – jbapple
    Commented Aug 17, 2011 at 0:46
-1
$\begingroup$
def F(a,b):
    M = max(max(a),max(b))
    C = BitArray of size M
    FOR x in a:
         C[x] = 1
    FOR y in b:
         C[y] = 1
    FOR z in range(0,M):
        IF C[z] == 1:
          c.append(z)
    return c

Nice qualities:

  1. This function is $O(n)$.
  2. It preserves order.

Non-nice qualities:

  1. If input is $a = [100000000000], b=[0]$ you will regret using it.

So if numbers in the lists are uniformly and densely distributed between $0$ and $M$ then this will work fine otherwise not using it will be wise.

But again the complexity is $O(n)$ and this is theoretical cs website.

$\endgroup$
2
  • $\begingroup$ I don't think the last one works. $\endgroup$
    – Kaveh
    Commented Aug 16, 2011 at 16:31
  • $\begingroup$ @Kaveh You are right. It doesn't. I tried to implement it just now. Needs many modifications. Thanks! $\endgroup$ Commented Aug 16, 2011 at 16:53

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.