EugeneJudo's blog

By EugeneJudo, history, 3 years ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?