# Notación Big O

> Una forma abreviada de decir cuánto crece el trabajo de un algoritmo con más datos.

- Nivel: Avanzado
- Temas: Software
- URL: https://tidbit.legios.com.ar/es/big-o-notation/
- En inglés: [Big O notation](https://tidbit.legios.com.ar/big-o-notation/)

La **notación Big O** (o notación O grande) describe cómo crece el tiempo (o la memoria) que usa un algoritmo a medida que crece la cantidad de datos, sin importar los detalles de una computadora en particular. No dice "esto tarda 2 segundos"; dice "si duplicás los datos, tarda más o menos el doble" o "cuatro veces más". Se escribe `O(n)`, `O(n²)` y así, donde `n` es el tamaño de la entrada.

Unas pocas clases cubren casi todos los casos cotidianos. `O(1)`, constante: leer el elemento 500 de un arreglo, o buscar una clave en una tabla hash, tarda más o menos lo mismo haya los datos que haya. `O(log n)`, logarítmica: la búsqueda binaria en una lista ordenada de un millón de elementos necesita unas 20 comparaciones, porque cada paso descarta la mitad. `O(n)`, lineal: revisar cada elemento una vez. `O(n log n)`: los buenos métodos de ordenamiento de uso general. `O(n²)`, cuadrática: comparar cada elemento con todos los demás, bien para cien, un sufrimiento para un millón.

La notación describe el peor caso y se queda solo con la parte que domina cuando `n` se hace grande, así que `3n + 50` es simplemente `O(n)`. Por eso importa en la práctica: un pedazo de código cuadrático que andaba al instante en las pruebas con 1.000 filas puede tumbar un servicio en producción con 1.000.000, porque el trabajo se multiplicó por un millón y no por mil. Los ingenieros usan Big O para comparar enfoques antes de escribirlos y para explicar por qué algo se puso lento.

## Una analogía

Organizar una fiesta. Mandar un mensaje al grupo cuesta lo mismo con 10 o con 100 invitados, O(1). Escribirle una tarjeta a cada uno crece con la lista, O(n). Presentar a cada invitado con todos los demás explota, O(n²).

## Para quedarse

- Describe cómo crece el trabajo con los datos, no los segundos exactos.
- Clases comunes: O(1), O(log n), O(n), O(n log n), O(n²).
- Solo cuenta el término que domina: 3n + 50 es O(n).
- Explica por qué un código rápido en las pruebas se arrastra a escala real.

## Para seguir leyendo

- [Cota superior asintótica (Big O) en Wikipedia](https://es.wikipedia.org/wiki/Cota_superior_asintótica)
- [Complejidad temporal en Wikipedia](https://es.wikipedia.org/wiki/Complejidad_temporal)

## Términos relacionados

- [Algoritmo](https://tidbit.legios.com.ar/es/algorithm/): Un método preciso, paso a paso, para resolver un problema o hacer una tarea.
- [Hashing](https://tidbit.legios.com.ar/es/hashing/): Una huella digital de los datos en un solo sentido: fácil de calcular, imposible de revertir.
