4
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.