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$
  • 2
    $\begingroup$ Are you asking for a way to compute the union of two lists? $\endgroup$ – Maverick Woo Aug 16 '11 at 9:12
  • 3
    $\begingroup$ I don't think this is a research level question. $\endgroup$ – Pratik Deoghare Aug 16 '11 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$ – Suresh Venkat Aug 16 '11 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$ – Radu GRIGore Aug 16 '11 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$ – Tsuyoshi Ito Aug 16 '11 at 14:51
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$
  • $\begingroup$ I ignored the phrase "average case" in the title, because it didn't appear in the question itself. $\endgroup$ – Jeffε Aug 20 '11 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$
  • 2
    $\begingroup$ I don't think the OP is assuming the original sequences are sorted. $\endgroup$ – Suresh Venkat Aug 16 '11 at 11:41
  • 2
    $\begingroup$ If the lists are sorted, then you just merge them (no need for fancy trees). $\endgroup$ – Radu GRIGore Aug 16 '11 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 Aug 16 '11 at 14:40
  • 1
    $\begingroup$ Can you build the finger tree faster than O(k)? $\endgroup$ – Radu GRIGore Aug 16 '11 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 Aug 17 '11 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$
  • $\begingroup$ I don't think the last one works. $\endgroup$ – Kaveh Aug 16 '11 at 16:31
  • $\begingroup$ @Kaveh You are right. It doesn't. I tried to implement it just now. Needs many modifications. Thanks! $\endgroup$ – Pratik Deoghare Aug 16 '11 at 16:53

Your Answer

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

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