- Hello Kaveh,

> I have two sets (A and B) of n positive integers each, and I need to

Consider the sets A = { N, 2N, 3N, ... N^2 }, B = { 0, 1, 2, ... N-1 }.

> 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.

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 - On 11/9/06, David Cleaver <wraithx@...> wrote:
> Anyway, wouldn't this be an O(2n-1) = O(2n) = O(n) operation? You could

I think he's talking about making the nxm table of all the differences

> 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?

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 - On 11/9/06, Peter Kosinar <goober@...> wrote:
> Consider the sets A = { N, 2N, 3N, ... N^2 }, B = { 0, 1, 2, ... N-1 }.

Hi Kaveh,

> 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 [*].

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