Sorry, an error occurred while loading the content.

## Notes on my "Fourier transform" question

Expand Messages
• The elements of my sets are random positive integers, and I need all n^2 values of (an element of A) - (an element of B). In fast multiplication using fast
Message 1 of 1 , Nov 9, 2006
• 0 Attachment
The elements of my sets are random positive integers, and I need all
n^2 values of (an element of A) - (an element of B).

In fast multiplication using fast fourier transform, the
conventional O(n^2) complexity reduces to O(n Ln(n)). So I wonder if
a similar trick might help speed up my task.

Awaiting your feedbacks.

Kaveh

- Response to David: No, they're not necessarily primes. And because
I need all n^2 values, it is (if done one by one) O(n^2).

- Response to Peter: Fast multiplication runs in O(n Ln(n)).
So "any" algorithm that handles two sets is not necessarily
quadratic.

- Response to Joshua: You got it right. I need all the elements and
it's O(nm), unless we come up with a trick like FFT, which I am
looking for.
Your message has been successfully submitted and would be delivered to recipients shortly.