# Efficient algorithm for computing the number of ways $a$ and $b$ from different ordered sets can be summed such that $a + b \leq x$, $x \in Z$

Let $$A$$ and $$B$$ be ordered (ascending) sets of integers, and let $$x \in Z$$. Design an efficient algorithm (in # of steps) for computing the number of different ways an element of $$A$$ can be summed with an element of $$B$$ such that their sum is less than or equal to $$x$$. Set elements may be in the order of $$10^{12}$$.

Fix $$b$$ to be the least element of $$B$$, then perform binary search over $$A$$ in order to find the greatest element of $$A$$, lets call it $$a$$, such that $$a + b \leq Z$$. Having found such element and its index $$i$$, we can be sure for all elements $$a' \in A, a' < a, a' + b \leq Z$$. Thus, we have $$i$$ ($$i+1$$, if the index starts at $$0$$) solutions with $$b$$. Now select the successor of $$b$$, and perform the same binary search over $$A$$. This will yield $$i_{2}$$ new solutions. You can do this until you find an element of $$B$$ whose sum with the first element of $$A$$ is greater than $$Z$$. The algorithm that follows such steps should do so in about $$\mathcal{O}(log(\lvert A\rvert$$)|B|)