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.