Hi Kaveh,

My method would be O(n^3) for what you want to do, but the idea is:

instead of computing anything ahead of time, if you ask "is k in the

set?" look at the k sums formed by adding an element of B to k, and

then check whether any of those is equal to an element of A.

Since that can be done with a hash table lookup, it can be quite fast

(you don't need to check every element of A, just look up whether your

value of "k+b" is in the hash table or not.

As for your actual question, since you don't need to compute all the

differences it is possible that there'd be a faster algorithm. There

are some obvious algorithms that *can* be fast (especially if there's

a missing number that is small) but most of the ones that occur to me

off the top of my head are still going to be O(nm) in the worst case

(because they have to check all nm results in the case where they are

all covered). I'll give it some more thought!

--Joshua Zucker

---------- Forwarded message ----------

From: Kaveh <

kaveh_vejdani@...>

Date: Nov 9, 2006 11:30 PM

Hi Josh, Peter, and David,

Thanks for your very helpful notes. I actually don't need to store

all the results. Let c be the largest difference of two elements

from A and B. In the case of my numbers, c~nm. All I need to know is

whether the entire range of [0,c] will be covered from pairwise

subtractions of the elements of A and B or not. Can this be done in

something better than O(nm)? I'm not sure if I'm following your O

(n+m) lookup method. How does it work?

Thanks.

Kaveh