Estoy tratando de calcular la complejidad del siguiente método en notación Big O
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; } }Entonces, primero hay un bucle que tiene O (n) y luego hay un bucle anidado y una función de prueba de primalidad, lo que significa que la complejidad de todo es O (n * m * sqrt (c))?
¿Puede confirmar si mi comprensión es correcta?
El bucle for (let i = 0; i < n.length; i++) se ejecuta n veces. La función m.filter((x) => x === n[i]).length comprueba todos los elementos en m, por lo que ejecuta m veces. Entonces tenemos un tiempo de ejecución de O(n*m).
Considerando
if (PrimalityTest(total)) { result.push(n[i]); }se ejecuta n veces porque está en el mismo bucle que el anterior. Entonces, en el peor de los casos, es O (n * sqrt (c))
Para resumir: es O(n*m)+O(n*sqrt(c)). Como O(n*m) supera a O(n*sqrt(c)) obtenemos como resultado: O(n*m).
Su solución significaría que la función de filtro integra el método PrimalityTest.