Home > Mobile >  What is the complexity for this algorithm?
What is the complexity for this algorithm?

Time:11-11

I'm learning big O notation and solving some problems, since i'm very new to this subject, i would like to know the complexity of this algorithm.

function findSum(arr,value){
    const set = new Set();
    for (let val of arr) {
      set.add(val);
    }
  
    const res = [];
    
    for (let val of set) {
      const target = value - val
      if (set.has(target)) {
        res.push(val, target);
        break;
      }
    } 
    return res.length > 0 ? res : false;
  }

CodePudding user response:

Let's break it down:

set.add() is an O(1) operation, hence the first part is clearly O(n), with n being the length of array.

set.has() is also O(1) (the whole point of hash-based data structures), and so is res.push() (appending to an array). That means that the second part (traversing the set) is also O(n).

Therefore the whole function is O(n).

  • Related