Notes on my "Fourier transform" question
- View SourceThe 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.
- 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
- 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