Fastest algorithm to perform N*M iterations in Python

Question

I am not an algorithm person, so pardon the naivety of the question.

I have a list A containing elements 100K elements. I have another list B containing 100K elements. Let's say a is an element from list A, b is the element from list B. I want to find out those (a, b) combinations whose sum is less than 100.

One obvious way to do this is following:

results = []
for a in A:
    for b in B:
        if (a+b) < 100:
            results.append((a,b))     

but the time complexity of this approach is O(n*m) = 100K * 100K which is quite large. Is there any fast algorithm which can compute the desired output more efficiently - in terms of memory and time. If yes, can it be implemented in python?

Answer 1

Sort both lists (O(n log n) and O(m log m), maybe less if the values are constrained).

Then, you can simply find, for each a in A, the largest b in B such that (a+b) < 100. Every smaller b will also satisfy that condition.

Finding the largest b for some a can be done using binary search to find a lower bound in B. And by starting with the largest a going down, you can preserve the list of bs corresponding to the previous a, since the sum is going to be smaller.

Answer 2

No you can't get better than that in the worst case. Consider a pathological case where every combination of A and B must be appended to the list:

A = list(range(0, -n, -1))
B = list(range(0, -m, -1))

Because each pair must be appended, you are doing O(m * n) operations.

If you only needed to count the number of combinations this could be a different story.