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?

Improve this question
$\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$ Commented Jul 12, 2018 at 9:39

1 Answer 1

Reset to default
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.

Improve this answer
$\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$ Commented 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$ Commented Jul 12, 2018 at 10:01

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.