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

Question

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.

Answer 1

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.