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