# Joining lists with some common elements in average case

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?

• Are you asking for a way to compute the union of two lists? Aug 16 '11 at 9:12
• I don't think this is a research level question. Aug 16 '11 at 10:21
• 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 Aug 16 '11 at 11:46
• If the input sequences are possibly not sorted, then I don't see what's the point of saying you have two sequences. Aug 16 '11 at 13:35
• To the asker: Please edit the question to clarify whether the input sequences are already sorted or not. −1 for this ambiguity. Aug 16 '11 at 14:51

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].

• I ignored the phrase "average case" in the title, because it didn't appear in the question itself. Aug 20 '11 at 22:41

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.

• I don't think the OP is assuming the original sequences are sorted. Aug 16 '11 at 11:41
• If the lists are sorted, then you just merge them (no need for fancy trees). Aug 16 '11 at 13:34
• @Radu GRIGore: Yes, but then you may make O(k) comparisons, which is not so great if i is small. Aug 16 '11 at 14:40
• Can you build the finger tree faster than O(k)? Aug 16 '11 at 14:59
• @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. Aug 17 '11 at 0:46
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.

• I don't think the last one works. Aug 16 '11 at 16:31
• @Kaveh You are right. It doesn't. I tried to implement it just now. Needs many modifications. Thanks! Aug 16 '11 at 16:53