Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
Is the actual assignment publicly available? Might be interesting whether the poorly-specified part actually matters here. –  G. Bach Feb 17 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 at 3:37
1  
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 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 at 3:48
2  
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 at 17:58
show 11 more comments

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
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 at 5:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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