CODEWITHSUNDEEP
algorithmtime-complexitybig-o
johnjoker13
johnjoker13

Reputation: 35

What is the complexity for this algorithm?

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;
  }

Upvotes: 0

Views: 36

Answers (1)

Tomer Ariel
Tomer Ariel

Reputation: 1537

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 is to enable constant time lookups), 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).

Upvotes: 1

Related Questions