CODEWITHSUNDEEP
javascriptalgorithmperformancetime-complexity
Bret Cameron
Bret Cameron

Reputation: 473

Does this JavaScript function have a linear or quadratic time complexity?

I'm trying to get my head around this solution in a Google interview video: https://youtu.be/XKu_SEDAykw?t=1139.

Though they say it is linear in the video, I'm not 100% certain if (and why) the entire solution is linear rather than quadratic?

Because the find()/includes() method is nested in the for loop, that would make me assume it has a run-time of O(N * N).

But find()/includes() is searching an array that grows 1 step at a time, making me think the run-time in fact just O(N + N)?

Here's my version of the solution in JavaScript:

const findSum = (arr, val) => {
  let searchValues = [val - arr[0]];
  for (let i = 1; i < arr.length; i++) {
    let searchVal = val - arr[i];
    if (searchValues.includes(arr[i])) {
      return true;
    } else {
      searchValues.push(searchVal);
    }
  };
  return false;
};


My workings:

Shouldn't that imply a linear run-time of O(N + (N - 1))? Or am I missing something?!

Thanks for your help!

Upvotes: 2

Views: 302

Answers (1)

Jonas Wilms
Jonas Wilms

Reputation: 138317

Yes, your solution is quadratic, because as you mentioned .includes traverses the array, so does for. In the interview however they talk about an unordered_set for the lookup array, which implies that this could be implemented as a HashSet, which has O(1) lookup/insertion time, making the algorithm O(n) (and O(n²) worst, worst case). The JS equivalent would be a Set:

 const findSum = (arr, sum) =>
  arr.some((set => n => set.has(n) || !set.add(sum - n))(new Set));

Upvotes: 1

Related Questions