Comparación de la complejidad de O (n + m) y O (max (n, m))
Tuve una entrevista de trabajo hoy. Y se le preguntó sobre la complejidad destd:set_intersection
. Cuando estaba respondiendo, mencioné que
O (n + m)
es igual a:
O (max (n, m))
Me dijeron que esto es incorrecto. Intenté sin éxito mostrar equivalencia con:
O (0.5 * (n + m)) ≤ O (max (n, m)) ≤ O (n + m)
Mi pregunta es: ¿soy realmente incorrecto?