# Asymptotic lower bound on the number of comparisons needed to find the intersection of unsorted arrays

A homework problem in my current CS class asks us to produce a comparison-based procedure for taking (essentially—there are some poorly-specified rules about duplicates) the set intersection of $$k$$ unsorted arrays of at most $$n$$ elements each. For full credit, we are supposed to do this in $$O((k-1)n)$$ comparisons. (Specifically, we are given a Java array of arrays of Comparable elements.)

I'm pretty thoroughly convinced that this is impossible, and that the best worst-case comparison bound for such a procedure is $$\Theta(N\log n_0)$$, where $$N$$ is the sum of the lengths of the arrays and $$n_0$$ is the length of the shortest array. I don't, however, know how to prove this is the best.

Since producing such an algorithm is current homework, please adhere to the following restriction in your answers/comments: if I am wrong, and it is possible to do better, do not reveal the algorithm unless it is very difficult (in which case a link to a relevant paper would be appreciated).

### What I've tried so far

The shortest array has $$2^{n_0}$$ subsets. This gives an immediate information-theoretic lower bound of $$\Omega(\log_2(2^{n_0}))$$. Unfortunately, this is just $$\Omega(n_0)$$, and $$O(n_0)$$ obviously can't be obtained.

### Edit

I missed a line in the (rather long) assignment. It looks like what he's looking for is actually a lot less interesting than what I thought he wanted. However, I'm still curious about how to prove a lower bound of $$\Omega(N \log n_0)$$, if that is the lower bound.

• Is the actual assignment publicly available? Might be interesting whether the poorly-specified part actually matters here. – G. Bach Feb 17 '14 at 3:33
• @G.Bach, no, it is not. The partial specification does make it clear that if an element is repeated the same number of times in each input array, then it should be repeated that many times in the output array. But to simplify matters, I'll be as lax as possible: for the purpose of answering this question, you can assume that the input arrays contain no duplicates. – dfeuer Feb 17 '14 at 3:37
• Hm, this sounds tricky. Comparison-based I can't do it, and I assume the using-a-hashmap-as-histogram approach is obvious to you anyway. – G. Bach Feb 17 '14 at 3:44
• @G.Bach, we only have a comparison function available, no hash function and no idea what the underlying type might be. I can't do it with comparisons either, but I don't know enough computational theory proof techniques to have a clue how to prove it impossible (if it is, in fact, impossible). – dfeuer Feb 17 '14 at 3:48
• Please make sure to update with an answer once they tell you how it works. I won't be able to get this out of my head before that. – G. Bach Feb 17 '14 at 17:58

I think we can prove that $O(n)$ time is not attainable for the special case $k=2$, using an adversary argument.

Fix a constant $c>0$. Let's take two lists of $n$ items, where the resulting $2n$ items are all different. Consider an algorithm that has done $cn$ comparisons between the $2n$ items in the two lists. This defines a partial order $\preceq$ on the $2n$ items, where if the algorithm has compared $x,y$, we have either $x \prec y$ or $y \prec x$, and where we let $\preceq$ be the reflexive, antisymmetric, transitive closure of $\prec$.

I'm pretty sure that, with high probability over the choice of the lists, there exists some item $x$ in the first list and some item $y$ in the second list such that $x,y$ are incomparable under $\preceq$. (This needs proof; I'll let you fill this part in.)

Now we can consider a parallel universe where everything is exactly the same as before, except that in the alternate universe, $y=x$. This alternate universe is also compatible with all of the comparisons that have been made by the algorithm. Thus, the algorithm cannot distinguish these two universes, so it must produce the same output in both cases.

However, the correct output for the two universes differs. The correct output in the first universe is the empty set, while the correct output in the second universe is the element $\{x\}$. Consequently, the algorithm must be incorrect in at least one of these two universes. In other words, for at least one of these two inputs, the algorithm produces the wrong output.

It follows that, when $k=2$, any $O(n)$-time algorithm must produce an incorrect answer on at least one input. In other words, any correct algorithm must take $\omega(n)$ time.

• Yes, there are a lot more partial orders than total orders. I think it may even be sufficient for this purpose to consider the partial orders that totally order subsets, but I'm not sure about that. – dfeuer Feb 17 '14 at 5:37