<p>In the algebraic decision/computation tree models, your problem has an $\Omega(n\log n)$ lower bound, even if you know in advance that one of your lists contains the integers $1$ through $n$ in sorted order, and you only need to check whether the second list is a permutation of the first.</p>

<blockquote>
  <p><strong>Proof (for algebraic computation trees):</strong> The set of points whose coordinates are permutations of $(1,2,\dots,n)$ has $n!$ components. Ben-Or proved that for any algebraic computation tree of height $h$, the set of points in $R^n$ that reach YES leaves has at most $2^h 3^{n+h}$ components. Solve for $h$.</p>
</blockquote>

<p>If you are restricted to equality tests, an $\Omega(n^2)$ lower bound follows from a straightforward adversary argument.</p>

CC BY-SA 3.0
2014-06-03T22:54:35.000Z
2014-06-04T12:57:10.110Z
2014-06-04T12:57:10.110Z
Jeffε
<p>Suppose you are given two lists $L_1$ and $L_2$, each of which contains pairwise distinct elements from some set $S$.</p>

<p><strong>What is the complexity of computing the intersection $L_1\cap L_2$ of the two lists?</strong></p>

<p>If you have an order on $S$, you can sort your both lists and then compute the intersection in linear time, achieving $O(n\log n)$ complexity where $n=\max(|L_1|,|L_2|)$. More specific questions are then:</p>

<ul>
<li>Can you compute the intersection in linear time, or at least faster than $O(n\log n)$?</li>
<li>If there is no natural order on $S$, what complexity can you achieve <em>without using a sorting algorithm</em>?</li>
</ul>

<p>The second bullet point is quite vague. What I want to understand is whether sorting the lists (or one of them) is necessary though the answer does not need to be sorted.</p>

CC BY-SA 3.0
2014-06-02T21:22:51.180Z
Maybe you already know this but related topic is known as [element distinctness problem](http://en.wikipedia.org/wiki/Element_distinctness_problem).
Saeed
CC BY-SA 3.0
2014-06-02T21:25:03.087Z
Related question http://stackoverflow.com/q/8102478/58737
Pratik Deoghare
CC BY-SA 3.0
2014-06-02T21:41:47.220Z
This has an easy linear time hashing-based solution that strikes me more as being at an undergraduate homework level than research.
David Eppstein
CC BY-SA 3.0
2014-06-03T08:05:57.660Z
@DavidEppstein: I agree with you, I should have posted my question on cs.stackexchange. Yet, even though it was not precisely stated, I am interested in worst-case deterministic complexity. I doubt a hashing-based solution achieves linear time in these settings.
Bruno
CC BY-SA 3.0
2014-06-03T09:36:08.193Z
How do you represent the elements?  If they are bit strings that can have arbitrary length, then you likely can't have a worst case runtime even polynomial in *n* because a single string can be longer than $ \Omega(n) $.  If your elements have a bounded length, then you can sort in $ O(n) $ time.  If you mean something in between, what exactly?
Zsbán Ambrus
CC BY-SA 3.0
2014-06-03T10:23:27.967Z
@ZsbánAmbrus, We usually talk about integer RAM model, so your point I think is not concern here, see [this](http://cs.stackexchange.com/questions/1643/how-can-we-assume-that-basic-operations-on-numbers-take-constant-time). I'm agree with Bruno, that perhaps this is easy but I doubt that if it's that easy. I think some way around using r-lists can show that in comparison model this cannot be done in $o(n\log n)$, and hashbased solution has a bad worst case (hash is not that blackbox magic we expect in theory, but in practice is really a magic).
Saeed
CC BY-SA 3.0
2014-06-03T10:32:49.180Z
If one of your list has been already stored into a cuckoo hashing based hash-table, than you get worst-case linear time, owing to the fact that cuckoo hashing guarantees worst-case constant lookup time (but insertions require expected constant time; that is why I have asked if you allow neglecting the expected linear time required for building the hash-table initially).
Massimo Cafaro
<ds.algorithms>
Intersection of two unsorted sets or lists
Bruno
# Intersection of two unsorted sets or lists

(Asked by: username_0 on 2014-06-02)

Suppose you are given two lists $L\_1$ and $L\_2$, each of which contains pairwise distinct elements from some set $S$.

**What is the complexity of computing the intersection $L\_1\cap L\_2$ of the two lists?**

If you have an order on $S$, you can sort your both lists and then compute the intersection in linear time, achieving $O(n\log n)$ complexity where $n=\max(|L\_1|,|L\_2|)$. More specific questions are then:

* Can you compute the intersection in linear time, or at least faster than $O(n\log n)$?
* If there is no natural order on $S$, what complexity can you achieve *without using a sorting algorithm*?

The second bullet point is quite vague. What I want to understand is whether sorting the lists (or one of them) is necessary though the answer does not need to be sorted.

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: Maybe you already know this but related topic is known as [element distinctness problem](http://en.wikipedia.org/wiki/Element_distinctness_problem).  
> **username_2**: Related question http://stackoverflow.com/q/8102478/58737  
> **username_3**: This has an easy linear time hashing-based solution that strikes me more as being at an undergraduate homework level than research.  
> **username_0**: @DavidEppstein: I agree with you, I should have posted my question on cs.stackexchange. Yet, even though it was not precisely stated, I am interested in worst-case deterministic complexity. I doubt a hashing-based solution achieves linear time in these settings.  
> **username_4**: How do you represent the elements?  If they are bit strings that can have arbitrary length, then you likely can't have a worst case runtime even polynomial in *n* because a single string can be longer than $ \Omega(n) $.  If your elements have a bounded length, then you can sort in $ O(n) $ time.  If you mean something in between, what exactly?  
> **username_1**: @ZsbánAmbrus, We usually talk about integer RAM model, so your point I think is not concern here, see [this](http://cs.stackexchange.com/questions/1643/how-can-we-assume-that-basic-operations-on-numbers-take-constant-time). I'm agree with username_0, that perhaps this is easy but I doubt that if it's that easy. I think some way around using r-lists can show that in comparison model this cannot be done in $o(n\log n)$, and hashbased solution has a bad worst case (hash is not that blackbox magic we expect in theory, but in practice is really a magic).  
> **username_5**: If one of your list has been already stored into a cuckoo hashing based hash-table, than you get worst-case linear time, owing to the fact that cuckoo hashing guarantees worst-case constant lookup time (but insertions require expected constant time; that is why I have asked if you allow neglecting the expected linear time required for building the hash-table initially).  

---

## 1 answers

### Answer by username_6 on 2014-06-03. Score: 8 | Accepted answer

In the algebraic decision/computation tree models, your problem has an $\Omega(n\log n)$ lower bound, even if you know in advance that one of your lists contains the integers $1$ through $n$ in sorted order, and you only need to check whether the second list is a permutation of the first.

> **Proof (for algebraic computation trees):** The set of points whose coordinates are permutations of $(1,2,\dots,n)$ has $n!$ components. Ben-Or proved that for any algebraic computation tree of height $h$, the set of points in $R^n$ that reach YES leaves has at most $2^h 3^{n+h}$ components. Solve for $h$.

If you are restricted to equality tests, an $\Omega(n^2)$ lower bound follows from a straightforward adversary argument.


---

