Explorador de complejidad Big-O

Big-O describe cómo crece el trabajo a medida que aumenta el tamaño de la entrada. Un único bucle crece aproximadamente con N, los bucles anidados suelen crecer con N², y la recursión ramificada puede crecer exponencialmente. La lección importante es la escala: con N pequeño, muchos enfoques se ven similares, pero con N grande la clase de crecimiento domina el tiempo de ejecución.

La forma más clara de percibir una clase de crecimiento es duplicar la entrada y observar qué le ocurre al trabajo. Con O(log N) apenas se mueve — la búsqueda binaria encuentra un elemento entre un millón en unas 20 comparaciones. Con O(N) el trabajo se duplica, y con O(N²) se cuadruplica. Desliza N en esta herramienta y verás cómo las distancias pasan de invisibles a abrumadoras.

Una clase de crecimiento menor no garantiza un programa más rápido. Los informáticos llaman a las excepciones algoritmos galácticos: métodos con mejor notación Big-O cuyo factor constante oculto es tan enorme que solo superan a los métodos sencillos con entradas mayores que cualquier cosa del universo físico. Varios algoritmos récord de multiplicación de matrices nunca se usan en la práctica justo por esto: Big-O descarta en silencio las constantes que deciden la velocidad real.