3
$\begingroup$

Suppose two equal-length lists of double precision numbers $A=(A_1, \ldots, A_N)$ and $B=(B_1, \ldots, B_N)$. Given a constant, $\epsilon > 0$, I want an efficient algorithm for finding 4-tuples of the form $(A_a, A_b, B_c, B_d)$ for which $|A_a + A_b - (B_c + B_d)| < \epsilon$.

One thing you could do is form the sum sets $S_A:=\{A_j + A_k\}$ and similarly, $S_B$, sort them, and then iterative over these in parallel looking for elements that satisfy the requirement.

This algorithm should have complexity of the form $O(N^2)$ (with perhaps a constant multiplicative factor). Forming the sum sets has complexity $\sim O(N^2)$, the sorting has complexity $\sim N \log N$; the final step is a single pass through both sum sets; also complexity $O(N^2)$.

Is there an algorithm that does better than $O(N^2)$?

$\endgroup$
2
$\begingroup$

I believe there is no known algorithm with running time faster than $O(N^2)$, even if you work with integers and ask for a tuple such that $A_a + A_b - (B_c + B_d) = 0$ (i.e., is exactly zero).

There are algorithms with running time $O(N^2)$ and space $O(N)$. Basically, they iterate through the sum sets $S_A$ and $S_B$ in order, without ever storing the entire sets in memory, by using a priority queue.

There are also algorithms that with running time $O(N^{4/3})$, if the numbers are chosen uniformly at random over some range and if you can choose $N$ appropriately (i.e., if the relationship between $N$ and the size of that range can be chosen appropriately) and if you only care about finding one such 4-tuple (even though many might exist). I suspect this probably isn't of use to you.

$\endgroup$

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.