1
$\begingroup$

Is there an algorithm to prepare all sums of pairs of a list ($L$, size $n$, max value $m$) in $< O(n^2)$ such that query "does this sum of pairs exist" takes $< O(n)$? In other words, can max value $m$ be used to advantage?

E.g. in $L =\{1, 2, 4, 8\}$ and $m = 8$, all (distinct) sums of pairs are $S = \{2, 3, 4, 5, 6, 8, 9, 10, 12, 16\}$ (not given, calculate).

This may be possible using a divide-and-conquer on both $L$ and on the bits of each item. (N.B. the constraint keeps $S.size$ to $2m$, no need for size $O(n^2)$)

$\endgroup$
  • $\begingroup$ How large is $m$ compared to $n$? $\endgroup$ – Chao Xu Jan 5 '15 at 9:41
7
$\begingroup$

Yes, it is possible using $O(n \log n)$ preprocessing and $O(\log n)$ query time.

Given the set $S$, construct the polynomial $P(x)=\Sigma_{s\in S}\textrm{ } x^s$. Then use the FFT multiplication algorithm to compute $P^2(x)=P(x)*P(x)$ in $O(n \log n)$.

A value $q$ s a sum-of-pairs of $S$ if and only if the coefficient of $x^q$ in $P^2(x)$ is non-zero. Use binary search to look up the coefficient in $O(\log n)$ time ($P^2(x)$ is a polynomial of degree $2m$).

There are also less complicated (and less efficient, but still better than $O(n^2)$) multiplication algorithms that use divide-and-conquer such as Karatsuba multiplication ($O(n^{1.585})$ preprocessing).

$\endgroup$
  • $\begingroup$ Given how special is the polynomial (all coefficients are 0 or 1), and that we are interested only in whether the coefficient in the product is non-zero, there probably should be a much simpler, or more efficient, multiplication algorithm than FFT? $\endgroup$ – jkff Jan 4 '15 at 22:16
  • $\begingroup$ Btw, seems like this problem is called "boolean convolution", though I couldn't yet find fast algorithms for it other than FFT. $\endgroup$ – jkff Jan 5 '15 at 6:56
  • 2
    $\begingroup$ Shouldn't the FFT take $O(m \log m)$ time instead? $\endgroup$ – Chao Xu Jan 5 '15 at 9:43
2
$\begingroup$

The value $m$ can be used to advantage by simply sorting the list, and applying whatever $O(n)$ algorithm you had in mind on the list pruned to exclude items greater than the requested sum (which is $< 2m$). You get $O(m + log(n))$ complexity then.

$\endgroup$
  • $\begingroup$ But you're not given $S$, you're given $L$ (I have clarified my question above). To get $S$ (brute force) takes $O(n^2)$, so the crux of my question was to find a better way to get $S$. The answer, turns out, is fast-fourier transform. $\endgroup$ – Derek Illchuk Jan 4 '15 at 22:28
  • $\begingroup$ Sorry for the confusion, by S I meant "the requested sum". It cannot be greater than 2m, and the rest of my answer holds. $\endgroup$ – jkff Jan 5 '15 at 1:15

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.