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

18409Re: [PrimeNumbers] Does Fourier transform help with exhaustive subtractions?

Expand Messages
  • Peter Kosinar
    Nov 9, 2006
    • 0 Attachment
      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
    • Show all 5 messages in this topic