# Intersection of two unsorted sets or lists

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.

• Maybe you already know this but related topic is known as element distinctness problem. Jun 2 '14 at 21:22
• Related question stackoverflow.com/q/8102478/58737 Jun 2 '14 at 21:25
• This has an easy linear time hashing-based solution that strikes me more as being at an undergraduate homework level than research. Jun 2 '14 at 21:41
• @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. Jun 3 '14 at 8:05
• 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? Jun 3 '14 at 9:36

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.