¿Cuál es la complejidad temporal?
def has_pair(nums):
for a in nums:
for b in nums:
if a != b and a + b == 0:
return True
return FalseOpciones
- O(n)
- O(n log n)
- O(n²) (Opción correcta)
- O(2n)
Respuesta
O(n²)
Por qué
Por cada uno de los n elementos del bucle exterior, el interior se ejecuta n veces: n × n = n² iteraciones.
O(n²) se llama cuadrático: con 1.000 elementos son cerca de 1.000.000 de comprobaciones; con 100.000 elementos, 10.000 millones.
Un set puede resolver este problema concreto en O(n).
Recuerda
Bucle dentro de bucle sobre los mismos datos = O(n²).