Fwd: Does Fourier transform help with exhaustive subtractions?
- 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!
---------- 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?