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;
}
>Solution :
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).