# 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

## 1 Answer

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.

• I thought about this option, but what if I take A to be an array of prime numbers, a sum of two primes is not a prime, so I won't have any duplicates. Which will result in O(n^2) different possabillities for the sums Jul 12, 2018 at 9:55
• I think I got it now, my previous examples with the primes does not work in this situation. Thanks. Jul 12, 2018 at 10:01