Loading ...
Sorry, an error occurred while loading the content.

Fwd: Does Fourier transform help with exhaustive subtractions?

Expand Messages
  • Joshua Zucker
    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
    Message 1 of 1 , Nov 10, 2006
    • 0 Attachment
      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
    Your message has been successfully submitted and would be delivered to recipients shortly.