Cómo medimos el costo

Big-O: cómo crece el trabajo con el tamaño de la entrada n — la vara de medir de todo el libro.

Cuenta operaciones, no segundos

Constante $O(1)$ — trabajo fijo, cualquier n
Lineal $O(n)$ — una pasada
Logarítmica $O(\log n)$ — parte la entrada a la mitad en cada paso
Quédate con el término dominante, descarta las constantes

La escalera

O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)

La forma es el costo del algoritmo. La constante es lo que compra tu hardware.

Las formas, creciendo

Búsqueda lineal vs binaria

Mismo objetivo, mismo array: 20 sondeos vs 5. Esa brecha es $O(n)$ vs $O(\log n)$ .

La librería cambia la constante, no la clase

Sort con n=16000: 15.6 ms desde cero vs 1.28 ms built-in (~12×)
La curva de la misma forma, con pendiente más suave
Gana el Big-O primero — ningún tuning rescata la forma equivocada

Conclusión

Hazle dos preguntas a cada algoritmo:

¿Cuál es el Big-O? (este capítulo)
¿Cuál es la constante? (el resto del libro)

1 / 7