La notación Big O describe cómo crece el trabajo al aumentar la entrada, sin tener en cuenta los factores constantes:
- O(1): el mismo trabajo para cualquier tamaño, como una búsqueda en un diccionario o conjunto.
- O(n): un recorrido de los datos.
- O(n log n): ordenar.
- O(n²): un bucle dentro de otro que recorre los mismos datos. Diez veces más filas supone cien veces más trabajo.
Algunos bucles se ocultan en una sola línea. x in a_list recorre la lista, por lo que hacerlo para cada elemento de otra lista es O(n²). x in a_set es O(1) en promedio, así que crear un conjunto una sola vez convierte todo el trabajo en O(n). Lo mismo ocurre con list.index, list.count y list.remove dentro de un bucle.
Otra técnica consiste en calcular una sola vez y reutilizar el resultado: los totales acumulados responden a cada pregunta de «suma desde i hasta j» con una sola resta.
En esta unidad, las comprobaciones ocultas usan entradas con miles de elementos. Una solución cuadrática supera el tiempo límite incluso si es correcta con pocos datos.
Salida: ['SO-1']. Cada in en el conjunto es un solo paso, no un recorrido de la lista.