Como sabemos, Array.prototype.some() y Array.prototype.includes() tienen una complejidad temporal de o(n). Ahora quiero saber si usaré include dentro de algún método. ¿La complejidad del tiempo será lineal o cuadrática?
function checkDublicate (arr1, arr2) { return arr1.some(item => arr2.includes(item)); }
Es O(mn) , donde m es arr1.length
y n es arr2.length
.
Considerando el peor de los casos, si arr2
no tiene elementos de arr1
, todos los n
elementos se buscarán en arr2
, y cada búsqueda tendrá una complejidad O(n)
. La complejidad general será O(n^2)
(suponiendo n
elementos en cualquier matriz).