Enconté mediante Reddit un post en Stack Overflow que explica en términos sencillos en qué consiste la notación “Big-O”, utilizada para representar la complejidad de un algoritmo.
Traduzco solo una parte del post aquí, les recomiendo leer el post completo si es que te encuentras en duda o necesitas repasar en qué consiste esta notación.
La notación Big-O es una representación relativa de la complejidad de un algoritmo.
Hay algunas palabras importantes deliberadamente elejidas en esta oración:
- relativa: únicamente puedes comparar manzanas con manzanas. No puedes comparar un algoritmo que hace multiplicación aritmética con uno que ordena una lista de enteros. No obstante, [comparar] dos algoritmos que hacen operaciones aritmeticas (uno multiplicación y otro suma) te dirá algo significativo.
- representación: Big-O (en su forma más simple) reduce la comparación entre algoritmos a una única variable. Esa variable es elegida basandose en observaciones y supuestos. Por ejemplo, [los] algoritmos para ordenar son típicamente comparados en base a operaciones de comparación (comparar dos nodos para determinar su orden relativo). Esto asume que comparar es costoso. ¿Pero qué si comparar es barato e intercambiar costoso? Cambia la comparación; y
- complejidad: si me toma un segundo ordenar 10.000 elementos, ¿cuánto me llevará ordenar un millón? La complejidad, en esta instancia, es una medida relativa de algo más.