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?
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.