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)
.