# Summing two array using FFT: time complexity analysis

This is the problem :

Given two arrays of $n$ elements A and B, let's define their sum as $$A + B = \{ a + b \mid a \in A \text{ and } b \in B \}.$$ Calculate $A + A$ in optimal time given that $A[i] \in [1,10n^{1.5}]$ for all $i$.

In order to solve this problem I used FFT by representing a polynomial in the following way:

$$p(x) = \sum_{i=0}^n x^{A[i]}.$$

After multiplying this polynomial with itself using FFT in linear time, I get the desired result in $\Theta(n^{1.5} \log n)$ time.

However, basic combinatorics gives us that there are $O(n^2)$ elements in the sum of $A + A$, How can I possibly produce them and copy them to a result array all in less than $O(n^2)$ using FFT?

• Note that is's also true to say that there are $O(2^n)$ elements in $A+A$ but that doesn't mean you need exponential time. $O(n^2)$ isn't $\Omega(n^2)$. Jul 12, 2018 at 9:39

Since all elements are in the range $[1,10n^{1.5}]$, all elements $A+A$ are in the range $[2,20n^{1.5}]$. So there are $O(n^{1.5})$ distinct elements in the sum. Some of them will be obtained more than once.