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

Does Fourier transform help with exhaustive subtractions?

Expand Messages
  • Kaveh
    Hi Everybody, I have two sets (A and B) of n positive integers each, and I need to subtract each element of B from each element of A. Obviously, the
    Message 1 of 5 , Nov 9, 2006
      Hi Everybody,

      I have two sets (A and B) of n positive integers each, and I need to
      subtract each element of B from each element of A. Obviously, the
      computation runs in O(n^2).

      I was wondering if fast Fourier transfrom can be used to reduce the
      time complexity of this task.

      I appreciate any feedbacks.

      Kaveh
    • David Cleaver
      I m not sure how this relates to primes, maybe the elements of A and B are all prime? *wishful thinking* Anyway, wouldn t this be an O(2n-1) = O(2n) = O(n)
      Message 2 of 5 , Nov 9, 2006
        I'm not sure how this relates to primes, maybe the elements of A and B
        are all prime? *wishful thinking*

        Anyway, wouldn't this be an O(2n-1) = O(2n) = O(n) operation? You could
        add up all elements of B and then subtract that sum from each element of
        A. Or are there additional restrictions you're not telling us about?

        BTW, its O(2n-1) because there are (n-1) additions performed in B, and
        then there are n subtractions in A. Since Big-O doesn't care about
        addends or constant multipliers, its really just O(n).

        -David C.

        Kaveh wrote:
        >
        >
        > Hi Everybody,
        >
        > I have two sets (A and B) of n positive integers each, and I need to
        > subtract each element of B from each element of A. Obviously, the
        > computation runs in O(n^2).
        >
        > I was wondering if fast Fourier transfrom can be used to reduce the
        > time complexity of this task.
        >
        > I appreciate any feedbacks.
        >
        > Kaveh
      • Peter Kosinar
        Hello Kaveh, ... Consider the sets A = { N, 2N, 3N, ... N^2 }, B = { 0, 1, 2, ... N-1 }. The set obtained by subtracting each element of B from each element of
        Message 3 of 5 , Nov 9, 2006
          Hello Kaveh,

          > I have two sets (A and B) of n positive integers each, and I need to
          > subtract each element of B from each element of A. Obviously, the
          > computation runs in O(n^2).
          >
          > I was wondering if fast Fourier transfrom can be used to reduce the
          > time complexity of this task.

          Consider the sets A = { N, 2N, 3N, ... N^2 }, B = { 0, 1, 2, ... N-1 }.
          The set obtained by subtracting each element of B from each element of A
          is { 1, 2, 3, ... N^2 }. In other words, the size of the resulting set can
          be quadratic and thus the worst-case runtime of any algorithm producing
          it is at least quadratic [*].

          Thus, without having some additional restrictions on the structure of the
          elements in those sets, the best you can hope for is a quadratic
          algorithm.

          Or did I misunderstood your problem statement?

          Peter

          [*] Assuming you're representing the set as an array of numbers.

          --
          [Name] Peter Kosinar [Quote] 2B | ~2B = exp(i*PI) [ICQ] 134813278
        • Joshua Zucker
          ... I think he s talking about making the nxm table of all the differences of (an element of A) - (an element of B). What I wonder about is what you want to do
          Message 4 of 5 , Nov 9, 2006
            On 11/9/06, David Cleaver <wraithx@...> wrote:
            > Anyway, wouldn't this be an O(2n-1) = O(2n) = O(n) operation? You could
            > add up all elements of B and then subtract that sum from each element of
            > A. Or are there additional restrictions you're not telling us about?

            I think he's talking about making the nxm table of all the differences
            of (an element of A) - (an element of B).

            What I wonder about is what you want to do with that table: sometimes
            it's O(n+m) if you just, say, want the total; O(nm) if you want all
            the elements; O(1) (but O(min(n,m)) for lookup) if you just want to
            check whether a few particular numbers occur or not ...

            --Joshua Zucker
          • Joshua Zucker
            ... Hi Kaveh, I think you misunderstood Peter s point (quoted above). With fast multiplication, n digits times m digits, the result will only have n+m digits,
            Message 5 of 5 , Nov 9, 2006
              On 11/9/06, Peter Kosinar <goober@...> wrote:
              > Consider the sets A = { N, 2N, 3N, ... N^2 }, B = { 0, 1, 2, ... N-1 }.
              > The set obtained by subtracting each element of B from each element of A
              > is { 1, 2, 3, ... N^2 }. In other words, the size of the resulting set can
              > be quadratic and thus the worst-case runtime of any algorithm producing
              > it is at least quadratic [*].

              Hi Kaveh,
              I think you misunderstood Peter's point (quoted above).

              With fast multiplication, n digits times m digits, the result will
              only have n+m digits, so Peter's argument says it takes at least
              O(n+m) time just to store the resulting bignum! And indeed FFT mult
              takes O(n ln n) which in general is way more than 2n.

              With your subtraction problem, n numbers minus each of m numbers, the
              result can have nm numbers, so he argues that since storing each
              number takes O(1) time, the whole computation must take at least O(nm)
              time. I think that argument sounds very convincing to me!

              My solution, which takes O(1) time, depends on not storing all the
              numbers, but rather on doing an O(n+m) lookup each time you want to
              check if a number is in the set "A-B" that you want. Peter already
              anticipated that, though, in his footnote which reminds us that the
              O(nm) minimum is only true if you want to store all the nm
              differences.

              So, if you really need all the numbers in a list, Peter is right and
              the minimum time is O(nm). If you can use some other way of
              remembering the numbers, or if you know some other properties of the
              numbers (like, say, the maximum is a lot less than nm, so you know
              there can't be nm different differences among them) then there might
              be an algorithm that exploits those other possibiities.

              --Joshua Zucker
            Your message has been successfully submitted and would be delivered to recipients shortly.