I'm trying to caluclate complexity of below method in Big O notation
function algorithm(n,m){
let result = [];
for (let i = 0; i < n.length; i++) {
const total = m.filter((x) => x === n[i]).length;
if (PrimalityTest(total)) {
result.push(n[i]);
}
}
return result;
};
function PrimalityTest(c){
if (c <= 1) {
return false;
} else if (c === 2) {
return true;
} else {
for (let i = 2; i * i <= c; i++) {
if (c % i === 0) {
return false;
}
}
return true;
}
}So, firstly there is loop which have O(n) and then there is nested loop and primality test function so that means complexity of all is O(n * m * sqrt(c))?
Can you please confirm If my understanding is correct?
The loop for (let i = 0; i < n.length; i++) is executed n times. The function m.filter((x) => x === n[i]).length checks every element in m, so executes m-times. So we have an execution time of O(n*m).
Considering
if (PrimalityTest(total)) {
result.push(n[i]);
}
is executed n times because it is in the same loop as above. So at worst it is O(n*sqrt(c))
To sum it up: It is O(n*m)+O(n*sqrt(c)). Because O(n*m) surpasses O(n*sqrt(c)) we get as result: O(n*m).
Your solution would mean that the filter function integrates the PrimalityTest method.