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

Expand Messages
• 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