Big-O describe cómo el tiempo de ejecución o la memoria de un algoritmo crecen conforme el tamaño de entrada n crece. Captura el comportamiento asintótico del peor caso, ignorando constantes y términos de orden inferior.
Nos importa la tasa de crecimiento, no los pasos exactos. O(2n + 5) es simplemente O(n) porque a medida que n crece, las constantes y términos menores dejan de importar.
| Big-O | Nombre | Ejemplo |
|---|
| O(1) | constante | búsqueda de índice en array |
| O(log n) | logarítmica | búsqueda binaria |
| O(n) | lineal | escaneo de lista |
| O(n log n) | linealítmica | merge sort |
| O(n²) | cuadrática | bucles anidados |
| O(2ⁿ) | exponencial | subconjuntos ingenuos |
def has_duplicate(nums):
for i in range(len(nums)): # outer loop: n
for j in range(i + 1, len(nums)): # inner loop: n
if nums[i] == nums[j]:
return True
return False
# nested loops -> O(n^2) time, O(1) space
Big-O oculta constantes: un algoritmo O(n) con una constante enorme puede perder contra O(n log n) en entradas pequeñas. También rastrea la complejidad del espacio, no solo el tiempo.
Big-O te permite comparar algoritmos sin ejecutarlos ni preocuparte por el hardware.
Predice qué soluciones sobreviven cuando las entradas crecen de cientos a millones — la diferencia entre una característica que escala y una que agota el tiempo.
Es el vocabulario que todo ingeniero usa para razonar sobre el desempeño.