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$
1
  • $\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$ Jul 12, 2018 at 9:39

1 Answer 1

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$
2
  • $\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, 2018 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, 2018 at 10:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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