<p>Yes and no.</p>

<p>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.</p>

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

CC BY-SA 3.0
2011-08-20T22:41:22.263Z
I ignored the phrase "average case" in the title, because it didn't appear in the question itself.
Jeffε
CC BY-SA 3.0
2011-08-20T22:39:52.263Z
2011-08-20T22:39:52.263Z
Jeffε
<p>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?</p>

<p>If so, you can represent the larger sequence as a special type of tree (a <a href="http://www.cs.au.dk/~gerth/papers/finger05.pdf" rel="nofollow">finger tree</a>), 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.</p>

CC BY-SA 3.0
2011-08-16T11:41:54.030Z
I don't think the OP is assuming the original sequences are sorted.
Suresh Venkat
CC BY-SA 3.0
2011-08-16T13:34:36.437Z
If the lists are sorted, then you just merge them (no need for fancy trees).
Radu GRIGore
CC BY-SA 3.0
2011-08-16T14:40:40.103Z
@Radu GRIGore: Yes, but then you may make O(k) comparisons, which is not so great if i is small.
jbapple
CC BY-SA 3.0
2011-08-16T14:59:37.000Z
Can you build the finger tree faster than O(k)?
Radu GRIGore
CC BY-SA 3.0
2011-08-17T00:46:53.310Z
@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.
jbapple
CC BY-SA 3.0
2011-08-17T14:18:22.953Z
No, the input "sequences" (would "lists" be more apropos?) are not necessarily sorted. Apologies for using incorrect terminology. I chose the term "sequences" over "sets" because each element corresponds to a certain index, which might be important for the code that inspired this question. On the other hand, treating inputs as sets might ensure commutativity if the algorithm is deterministic.
Harish Kukreja
CC BY-SA 3.0
2011-08-16T06:55:28.637Z
2011-08-16T06:55:28.637Z
jbapple
<pre><code>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
</code></pre>

<p><strong>Nice qualities:</strong>  </p>

<ol>
<li>This function is $O(n)$.   </li>
<li>It preserves order.    </li>
</ol>

<p><strong>Non-nice qualities:</strong>  </p>

<ol>
<li>If input is $a = [100000000000], b=[0]$ you will regret using it. </li>
</ol>

<p>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. </p>

<p>But again the complexity is $O(n)$ and this is <em>theoretical</em> cs website. </p>

CC BY-SA 3.0
2011-08-16T16:31:50.967Z
I don't think the last one works.
Kaveh
CC BY-SA 3.0
2011-08-16T16:53:23.240Z
@Kaveh You are right. It doesn't. I tried to implement it just now. Needs many modifications. Thanks!
Pratik Deoghare
CC BY-SA 3.0
2011-08-16T03:14:35.053Z
2011-08-16T16:56:17.400Z
2011-08-16T16:56:17.400Z
Pratik Deoghare
<p>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</p>

<p>$a = [5, 1, 6, 8]$</p>

<p>$b = [8, 4, 5, 2, 10]$</p>

<p>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.</p>

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

CC BY-SA 3.0
2011-08-16T09:12:54.643Z
Are you asking for a way to compute the union of two lists?
Maverick Woo
CC BY-SA 3.0
2011-08-16T10:21:06.513Z
I don't think this is a research level question.
Pratik Deoghare
CC BY-SA 3.0
2011-08-16T11:46:36.363Z
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
Suresh Venkat
CC BY-SA 3.0
2011-08-16T13:35:32.253Z
If the input sequences are possibly not sorted, then I don't see what's the point of saying you have *two* sequences.
Radu GRIGore
CC BY-SA 3.0
2011-08-16T14:51:34.950Z
To the asker: Please edit the question to clarify whether the input sequences are already sorted or not.  −1 for this ambiguity.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-17T14:25:56.013Z
The input sequences are not necessarily sorted. I chose the term "sequences" over "sets" because the indices of elements in both inputs might be relevant to surrounding code (a permutation of $a$ corresponds to a different iteration order, which in turn corresponds to a different output).

@Suresh Venkat: Thanks for the reference.
Harish Kukreja
CC BY-SA 3.0
2011-08-17T15:28:36.913Z
Thank you for the edit, but: (1) It would have been much clearer if you changed the example to one which does not suggests that the input is always sorted.  (2) I agree with Radu that I cannot see the point of saying that you have two lists if they are not sorted.  It seems to me that that is equivalent to having one input which is the concatenation of the two lists.  Moreover, finding duplicates in a list of elements is a well-known problem and may not be suitable on cstheory.stackexchange.com.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-18T03:16:05.420Z
Sorry for not being clear enough.  The use of the term “sequence” did not suggest that it is sorted (and the term “list” is as good as “sequence”).  It is your example that suggested that the input was sorted, and it still does.  But you should really think about Radu’s comment.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-21T17:24:13.940Z
The posted problem arises as a component of the following problem. Suppose we need to impose a specific ordering upon the keys of an associative array (e.g. mapping strings to floats), perhaps because we wish to work with the values in a consistent, vectorized form. Suppose the keys of {'a': 1.1, 'b': 3.2, 'c': 0.5} are ordered ('b', 'c', 'a') so as to produce a vector of values (3.2, 0.5, 1.1). The ordering ('b', 'c', 'a') is one of the inputs to the problem described in the original question. The output should be similarly ordered (the specific order is arbitrary, but should be consistent).
Harish Kukreja
<reference-request><ds.data-structures>
Joining lists with some common elements in average case
Harish Kukreja
# Joining lists with some common elements in average case

(Asked by: username_0 on 2011-08-15)

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?

**Tags:** reference-request, ds.data-structures

> **Comments:**
> **username_1**: Are you asking for a way to compute the union of two lists?  
> **username_2**: I don't think this is a research level question.  
> **username_3**: 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  
> **username_4**: If the input sequences are possibly not sorted, then I don't see what's the point of saying you have *two* sequences.  
> **username_5**: To the asker: Please edit the question to clarify whether the input sequences are already sorted or not.  −1 for this ambiguity.  
> **username_0**: The input sequences are not necessarily sorted. I chose the term "sequences" over "sets" because the indices of elements in both inputs might be relevant to surrounding code (a permutation of $a$ corresponds to a different iteration order, which in turn corresponds to a different output).  @username_3: Thanks for the reference.  
> **username_5**: Thank you for the edit, but: (1) It would have been much clearer if you changed the example to one which does not suggests that the input is always sorted.  (2) I agree with Radu that I cannot see the point of saying that you have two lists if they are not sorted.  It seems to me that that is equivalent to having one input which is the concatenation of the two lists.  Moreover, finding duplicates in a list of elements is a well-known problem and may not be suitable on cstheory.stackexchange.com.  
> **username_5**: Sorry for not being clear enough.  The use of the term “sequence” did not suggest that it is sorted (and the term “list” is as good as “sequence”).  It is your example that suggested that the input was sorted, and it still does.  But you should really think about Radu’s comment.  
> **username_0**: The posted problem arises as a component of the following problem. Suppose we need to impose a specific ordering upon the keys of an associative array (e.g. mapping strings to floats), perhaps because we wish to work with the values in a consistent, vectorized form. Suppose the keys of {'a': 1.1, 'b': 3.2, 'c': 0.5} are ordered ('b', 'c', 'a') so as to produce a vector of values (3.2, 0.5, 1.1). The ordering ('b', 'c', 'a') is one of the inputs to the problem described in the original question. The output should be similarly ordered (the specific order is arbitrary, but should be consistent).  

---

## 3 answers

### Answer by username_6 on 2011-08-20. Score: 4

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

> **Comments:**
> **username_6**: I ignored the phrase "average case" in the title, because it didn't appear in the question itself.  

---

### Answer by username_7 on 2011-08-16. Score: 0

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](http://www.cs.au.dk/~gerth/papers/finger05.pdf)), 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.

> **Comments:**
> **username_3**: I don't think the OP is assuming the original sequences are sorted.  
> **username_4**: If the lists are sorted, then you just merge them (no need for fancy trees).  
> **username_7**: @username_4: Yes, but then you may make O(k) comparisons, which is not so great if i is small.  
> **username_4**: Can you build the finger tree faster than O(k)?  
> **username_7**: @username_4 - 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.  
> **username_0**: No, the input "sequences" (would "lists" be more apropos?) are not necessarily sorted. Apologies for using incorrect terminology. I chose the term "sequences" over "sets" because each element corresponds to a certain index, which might be important for the code that inspired this question. On the other hand, treating inputs as sets might ensure commutativity if the algorithm is deterministic.  

---

### Answer by username_2 on 2011-08-16. Score: -1

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: 

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

Non-nice qualities: 

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.

> **Comments:**
> **username_8**: I don't think the last one works.  
> **username_2**: @username_8 You are right. It doesn't. I tried to implement it just now. Needs many modifications. Thanks!  

---

