4

Task - Consider an array of n elements. Count the number of pairs that satisfy condition X (sum of the two elements < an arbitrary number, k) .

The basic approach I could think of would be O(n^2), where I evaluate all n*(n-1)/2 pairs. How can I solve the problem in a better time frame i.e., O(n log n) or less?

The best approach so far was to sort the array, find where a+b smaller than k then add indice of a to solution. But the process still has to go through n-1 'b's to check for each of them. It's better but still doesn't improve the worst case.

Also, this isn't homework. I came across this while preparing for a competition.

  • 1
    As long as there is no restriction what the condition might be, there very likely is no faster way. If the condition is (anti-)symmetric and transitive there might be. – Patrick Nov 28 '13 at 9:05
5

if you need ALL results on an arbitrary condition (say C(a,b) = (sha1(a~c)^sha1(c~a))%2 == 0 with ~ as concatenation) then there are n*(n-1)/2 values you need to output that are all independent; so no there is no better way,

but if the result of one pair tells you something about the result of another pair then that information can be used to speed things up. like in your example if sum > k then you sort and for each number you check each in order (forwards or backwards). On the first true result you add the numbers still remaining. This will be O(n log n + r) with r number of true results.

edit: on second thought you can use a binary search each on each number a find the first number that is larger than k-a reducing it to a O(n log n) completely

  • I've tried that approach. Sort the array, find where a+b<k then add indice of a to solution. But the process still has to go through n-1 'b's to check for each of them. It's better but still doesn't improve the worst case. – 7Aces Nov 28 '13 at 9:16
  • 2
    @Neil: O(2 n log n) = O(n log n). So unless we really inspect the constant factors involved, we can't really tell anything more based on just the big-O notation. – Joachim Sauer Nov 28 '13 at 10:17
  • 1
    @Neil even n as low as 100 gives a big difference – ratchet freak Nov 28 '13 at 10:41
  • 1
    @Neil: no, we can't say that it's twice as long! That depends on the constant factors. If one O(n log n) operation has a constant factor (multiplier) of 5 and the other has one of 1, then they are together "O(2 n log n) = O(n log n)" but together only take 1.2 times as long as the first one alone. Either you look at all the precise performance characteristics (and thus leave big-O-land) or you stick to the rules and discard the constant factors. – Joachim Sauer Nov 29 '13 at 9:14
  • 1
    @Neil if you step away from Big O then you are doing profiling. doing theoretical profiling is a exercise in futility because it depends on too many thing that are impossible to control – ratchet freak Nov 29 '13 at 9:46
2

In that general way you explain it: no, can't be done.

As soon as you need to evaluate all pair combinations you pretty much have a O(n2) runtime.

If there is some way to exclude some combinations (for example for a given item, you know that no combination will fulfill the condition), then you can get better runtime behaviour.

For example, if you know the smallest number in your array to be min, then skipping all element e where e + min > k can help you get a better effective runtime (but it won't reduce the worst case).

Another approach that's useful if you don't need the best solution, but "good enough" is enough, is to use a heuristic. For example, if you can "guess" that a given item is unlikely to be in the ideal combination, you can skip it. This again will improve performance but can lead to you missing the ideal combination.

  • How about the particular condition X in the problem? – 7Aces Nov 28 '13 at 9:08
2

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 plus + 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 searched.

  1. Sort the array in O(n log n)

  2. 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).

  3. If A[i] + A[j] is greater than k then decrease i and try 3. again, otherwise go to 4.

  4. If A[i] + A[j+1] is smaller than k then increase j and try 4. again.

  5. We have found a point marked with a * add it to I and decrease i.

  6. If A[i] + A[j+1] is greater than k then decrease i and try 6. again.

  7. 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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.