What is the time complexity of Javascript Array.reduce() and Array.find()?

Question

I am trying to return an array of indexes of values that add up to a given target. I am trying to solve it the fastest way I can!

Examples:

sumOfTwo([1, 2, 4, 4], 8)   // => [2, 3]
sumOfTwo([1, 2, 3, 9], 8)   // => []

So first I tried a simple brute-force. (Time complexity: O(n^2) )

function sumOfTwo(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] + arr[j] === target) {
        return [i, j];
      }
    }
  }

  return [];
}

Then I tried: (Time complexity: sorting O(n log n) + for loop O(n))

function sumOfTwo(arr, target) {
  const sortedArr = arr.sort();
  let idxFromBack = arr.length - 1;

  for (let [idx, val] of sortedArr.entries()) {
    if (val + arr[idxFromBack] > target) {
      idxFromBack--;
    }

    if (val + arr[idxFromBack] === target) {
      return [idx, idxFromBack];
    }
  }

  return [];
}

Then I came with this solution that I don't even know the time complexity.

function sumOfTwo(arr, target) {
  const complements = [];

  for (let [idx, val] of arr.entries()) {
    if (complements.reduce((acc, v) => (acc || v.value === val), false)) {
      return [complements.find(v => v.value === target - val).index, idx];
    }

    complements.push({index: idx, value: target - val});
  }

  return [];
}

I know that I am using a for-loop but I don't know the complexity of the build-in high order functions .reduce() and .find(). I tried a couple of searches but I couldn't find anything.

If anyone can help me would be great! Please include Big-O notation if possible.

Repl.it: https://repl.it/@abranhe/sumOfTwo

---

Please also include the time complexity of the last solution.

Answer 1

The minimum time complexity of .reduce is O(n), because it must iterate through all elements once (assuming an error isn't thrown), but it can be unbounded (since you can write any code you want inside the callback).

For your

  // Loop, O(n), n = length of arr:
  for (let [idx, val] of arr.entries()) {
    // .reduce, O(n), n = length of complements:
    if (complements.reduce((acc, v) => (acc || v.value === val), false)) {
      // If test succeeds, .find, O(n), n = length of complements:
      return [complements.find(v => v.value === target - val).index, idx];
    }

    complements.push({index: idx, value: target - val});
  }

the time complexity is, worst case, O(n^2). The reduce runs in O(n) time, and you run a reduce for every entry in arr, making it O(n^2).

(The .find is also an O(n) operation, but O(n) + O(n) = O(n))

Your code that sorts the array beforehand has the right idea for decreasing complexity, but it has a couple flaws.

• First, you should sort numerically ((a, b) => a - b)); .sort() with no arguments will sort lexiographically (eg, [1, 11, 2] is not desirable).

• Second, just decrementing idxFromBack isn't enough: for example, sumOfTwo([1, 3, 8, 9, 9], 9) will not see that 1 and 8 are a match. Perhaps the best strategy here would be to oscillate with while instead: from a idxFromBack, iterate backwards until a match is found or the sum is too small, and also iterate forwards until a match is found or the sum is too large.

You can also improve the performance of this code by sorting not with .sort((a, b) => a - b), which has complexity of O(n log n), but with radix sort or counting sort instead (both of which have complexity of O(n + k), where k is a constant). The optimal algorithm will depend on the general shape and variance of the input.

An even better, altogether different O(n) strategy would be to use a Map or object. When iterating over the array, put the value which would result in a match for the current item into a key of the object (where the value is the current index), and just look to see if the current value being iterated over exists in the object initially:

const sumOfTwo = (arr, target) => {
  const obj = {};
  for (const [i, num] of arr.entries()) {
    if (obj.hasOwnProperty(String(num))) {
      return [obj[num], i];
    }
    const matchForThis = target - num;
    obj[matchForThis] = i;
  }
  return [];
};

console.log(
  sumOfTwo([1, 2, 4, 4], 8),   // => [2, 3]
  sumOfTwo([1, 2, 8, 9], 9),  // 1 + 8 = 9; [0, 2]
  sumOfTwo([1, 2, 3, 9], 8)   // => []
);

Answer 2

As a supplementary answer, here is the algorithm of the find method in the language spec:

When the find method is called, the following steps are taken:

1. Let O be ? ToObject(this value).

2. Let len be ? LengthOfArrayLike(O).

3. If IsCallable(predicate) is false, throw a TypeError exception.

4. Let k be 0.

5. Repeat, while k < len,

   a. Let Pk be ! ToString(𝔽(k)).

   b. Let kValue be ? Get(O, Pk).

   c. Let testResult be ! ToBoolean(? Call(predicate, thisArg, « kValue, 𝔽(k), O »)).

   d. If testResult is true, return kValue.

   e. Set k to k + 1.

6. Return undefined.

Note the "repeat, while k < len" in step 5. Since time complexity in general measures the worst case scenario (aka the upper bound), we can assume that the searched element is not present in the collection.

The number of iterations made during step 5 then is equal to len which directly depends on the number of elements in the collection. And what time complexity has a direct correlation to the number of elements? Exactly, the linear O(n).

For a visual-ish demonstration, run the following snippet. Apart from some stray dots, the improvized graph should show a linear progression (takes a little while to display in Stack snippets, but you can watch it live in the devtools console):

const iter = 1e7;
const incr = 2e5;

const test = new Array(iter).fill(0);
const steps = Math.ceil(iter / incr);

for (let i = 0; i < steps; i += 1) {
  const sub = test.slice(0, i * incr + incr);
    
  const s = Date.now();
  
  const find = sub.find((v) => v === 1);
  
  const e = Date.now();
  const d = e - s;
  
  console.log("\u200A".repeat(Math.floor(d/3))+"*");
}