2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – David Richerby Jul 12 '18 at 9:39
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Eliran Ziv Jul 12 '18 at 9:55
  • $\begingroup$ I think I got it now, my previous examples with the primes does not work in this situation. Thanks. $\endgroup$ – Eliran Ziv Jul 12 '18 at 10:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.