Finding complementary pairs

I've read the docs online explaining Log N and I do understand that the basic concept of it, but I'm still not sure I've managed to nail it.


The problem


This exercise is called "Complementary Pairs" and given an array A
and an integer K, how many pairs of A, sum to K.


For example, with this input:

k = 6 a = [1, 8, -3, 0, 1, 3, -2, 4, 5]

we would have 7 possibilities, like i, j = (5, 5) to add 3 + 3, then the
pairs that add 1 + 5 (and the reverse), etc.


Naive solution


A first very naive solution is to for a \$O(N^2)\$ complexity
loop where you just bluntly search the array in two nested loops.

\$N * Log N\$ Solution

From my understanding a proper \$Log N\$ solution has to include a binary search like quicksort or mergesort, so I applied a divide and conquer algorithm where I split the array in two, until it's down to one element, then I assemble back again, and I for a \$N*N\$ search on array, checking which elements of the first added with the second add to constant K.

Although this is very similar to mergesort, it just doesn't feel a \$N Log N\$ solution, because the worst case, the last recursion step, I'm doing \$N/2 N/2\$ and for me that's just \$N*N\$ over time.

Here is the working solution:

var complementary_pairs = function (input, k) {

  // Base scenario
  if (input.length == 1) {    
    return input[0] * 2 == k ? 1 : 0
  }

  // Recursion
  var middle = Math.ceil(input.length / 2)
    , firstArray = input.slice(0, middle)
    , secondArray = input.slice(middle)

  var count = complementary_pairs(firstArray, k)
    + complementary_pairs(secondArray, k)

  // Problem condition
  for (var i = 0; i < firstArray.length; i++) {
    for (var j = 0; j < secondArray.length; j++) {
      if (firstArray[i] + secondArray[j] == k) {
        count += 2
      }
    }
  }

  return count

}

console.log(complementary_pairs([1, 8, -3, 0, 1, 3, -2, 4, 5], 6))

This is not O(n log n) algorithm, because this part is quadratic:

for (var i = 0; i < firstArray.length; i++) {
    for (var j = 0; j < secondArray.length; j++) {
      if (firstArray[i] + secondArray[j] == k) {
        count += 2
      }
    }
  }

Denoting n = input.length, this has roughly (n/2)^2 = n^2/4 steps, which is O(n^2).

The rest of this answer is a result of a misread and is not directly related to the question. I'll leave it as a comment of a possibly extended exercise.

However, I'm not sure that O(n log n) algorithm does exist. Consider

a = [ 1, 2, 4, 8, ..., 2^n ] (for some n)

and k is a sum of all elements in a. Since you can repeat the numbers, and a[k] = 2*a[k-1] for all positive k, you'd have exponential number of sums, so no O(n log n) algorithm will solve this.

It is easy to show that the number of solutions is strictly bigger than 2^n. Just note that

k = (sum of ANY elements in a except a[0] = 1) + (sum of the remaining elements in a) * 1.

The first sum can be chosen in 2^n ways. Of course, there are other sums as well, but this is enough to show that you can have an exponential number of solutions, which is enough to show that no sub-exponential algorithm can find them all.

Of course, there may be a mathematical trick to compute only how many such solutions there are, but I don't know it.

StackExchange Code Review Q#31377, answer score: 4