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