FFT question

Revision en1, by EugeneJudo, 2021-09-22 05:19:02

I was looking over this article https://cp-algorithms.com/algebra/fft.html, and I was a bit confused by one of example applications. It says that we can use FFT to efficiently solve for all unique sums a[i] + b[j] given integer arrays a and b in $$$O(n\log(n))$$$. I follow the logic behind how the polynomial representation gives us this solution, but i'm confused by the following example: Say a = [1,2,...,1000] and b = [0,1000,2000,...,1000000], then all possible sums takes $$$O(n^2)$$$ to even store! Am I misunderstanding what $$$n$$$ refers to here?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English EugeneJudo 2021-09-22 05:19:02 567 Initial revision (published)