Si probás un algoritmo con 10 elementos y tarda 1 segundo, ¿cuánto tarda con 100? ¿2 segundos? ¿10? ¿100?
La respuesta depende de la forma del algoritmo. Eso es exactamente lo que mide BigO.
Qué es BigO Notation
BigO describe el comportamiento asintótico de un algoritmo: cómo crece el tiempo requerido (o el espacio en memoria) a medida que crece el tamaño del input n, en el peor caso.
No mide segundos reales — los segundos reales dependen del hardware, del lenguaje, del compilador, de si la luna está en cuarto menguante. BigO mide la forma del crecimiento, independiente de todos esos factores.
Cuando decimos que un algoritmo es O(n), decimos que si duplicás el input, el tiempo se duplica aproximadamente. Si es O(n²), duplicar el input cuadruplica el tiempo.
Las clases de complejidad
| Notación | Nombre | Ejemplo típico |
|---|---|---|
| O(1) | Constante | Acceso a un array por índice |
| O(log n) | Logarítmica | Binary search, operaciones en BST balanceado |
| O(n) | Lineal | Recorrer una lista |
| O(n log n) | Lineal-logarítmica | MergeSort, HeapSort |
| O(n²) | Cuadrática | Bubble sort, comparación de pares |
| O(2ⁿ) | Exponencial | Algoritmos de fuerza bruta sobre subconjuntos |
El orden importa en producción. La diferencia entre O(n) y O(n²) es irrelevante con 10 elementos. Con un millón de elementos, la diferencia es entre un proceso que tarda 1 segundo y uno que tarda 11 días.
Por qué "en el peor caso"
BigO mide el peor caso porque es lo que necesitás garantizar. Si tu sistema debe responder en menos de 100ms bajo cualquier condición, el promedio no te salva — el peor caso sí.
Dicho esto, hay variantes:
- Big-O — peor caso (la más usada)
- Big-Ω (Omega) — mejor caso
- Big-Θ (Theta) — cota ajustada: vale como techo y como piso a la vez
En el día a día de ingeniería, cuando alguien dice "es O(n)", generalmente habla del peor caso.
Cómo leer BigO en la práctica
O(1) — Constante. No importa el tamaño del input, el tiempo es el mismo. Acceder a array[42] es O(1) porque la dirección de memoria se calcula directamente.
O(log n) — Logarítmica. Cada paso descarta la mitad de los candidatos restantes. Binary search sobre un array ordenado: cada comparación elimina la mitad del espacio de búsqueda. Con 1 millón de elementos, necesitás a lo sumo 20 comparaciones.
O(n) — Lineal. El tiempo crece proporcionalmente al input. Buscar un elemento en una lista no ordenada requiere revisar cada elemento en el peor caso.
O(n²) — Cuadrática. Típico de algoritmos con dos loops anidados donde el interno recorre todo el array por cada elemento del externo. Aceptable para inputs pequeños. Catastrófico a escala.
O(2ⁿ) — Exponencial. Solo útil para inputs muy pequeños. Calcular todos los subconjuntos posibles de un conjunto es O(2ⁿ) — con 30 elementos ya hablamos de mil millones de operaciones.
La regla práctica
Cuando analizás complejidad, eliminás los términos no dominantes y las constantes. O(3n² + 5n + 2) se simplifica a O(n²) porque para inputs grandes, el término cuadrático domina completamente.
Esta simplificación es intencional: BigO describe la forma del crecimiento, no el valor exacto. Lo que importa es si tu algoritmo crece linealmente, cuadráticamente, o de alguna otra forma — el coeficiente exacto es un detalle de implementación.