Given an array A of length n and a bound k find all indices
(i,j) such that A[i] + A[j] < k.
This can actually be solved in O(n log n).
The set I of indices (i,j) you are looking for has some structure
when the array is sorted in increasing order. Indeed if (i₀,j₀)
belongs to I then, whenever i ≤ i₀ and j ≤ j₀ the indice pair
(i,j) also belongs to I. This means that I looks like this:
where a dot
. denotes a pair that does not belong to I while a
+ or a star
* denotes a pair belonging to I. As you see,
the presence of an indice denoted
+ is implied by the presence of
some indice denoted by a star
* so only the latter need to be
Sort the array in O(n log n)
Set i to the largest indice so that A[i] ≤ k in O(n) and set
j to 1 if you use Pascal or 0 if you use another language, this
latter operation is O(1).
If A[i] + A[j] is greater than k then decrease i and try 3.
again, otherwise go to 4.
If A[i] + A[j+1] is smaller than k then increase j and try 4. again.
We have found a point marked with a
* add it to I and decrease
If A[i] + A[j+1] is greater than k then decrease i and try 6. again.
Go to 4.
Do not forget to fix the algorithm and add boundary checking and
adequate exit conditions. In the repetitive part 3.-7. the algorithm
only visits indices that are on the frontier between I and its
complement. This frontier has length at most 2n so the overall cost
of this exploration is O(n). The repetitive part 3.-7. is just a contrived way to say: visit that frontier, remembering whenever you have to change direction.
The total cost of the algorithm is then O(n log n) + O(n) + O(1) +
O(n) = O(n log n).
P.S.: Actually the picture should be symmetric around the first diagonal and the algorithm can stop exploring the frontier when it meets the diagonal. These are small details.
P.P.S.: Of course, if your condition does not have structure, you must explore all combinations.