Notación Big O para principiantes: O(1), O(n), O(n al cuadrado) y O(log n) explicadas

Crecimiento, no tiempo de cronómetro

Big O no trata de cuántos segundos tarda algo en tu portátil. Trata de cómo escala el trabajo cuando la entrada crece. Dos algoritmos pueden ser ambos O(n), y aun así uno corre el doble de rápido en hardware real por un factor constante menor. Big O descarta a propósito esa constante, porque con n suficientemente grande la forma de la curva de crecimiento domina cualquier multiplicador fijo.

La notación también conserva solo el término que crece más rápido. Un algoritmo que hace 3n al cuadrado más 5n más 200 operaciones es simplemente O(n al cuadrado), porque una vez que n es grande el término al cuadrado empequeñece al resto. Por eso Big O es una lupa tosca pero potente: te da la clase de comportamiento, justo lo que necesitas al decidir si una solución sobrevivirá a cien veces más datos.

Las cuatro clases comunes

O(1) es tiempo constante: leer un elemento de arreglo por índice o comprobar una clave de mapa hash cuesta el mismo esfuerzo tenga la colección diez elementos o diez millones. O(log n) es logarítmico: la búsqueda binaria reduce a la mitad los datos restantes en cada paso, así que buscar en una lista ordenada de mil millones de elementos toma solo unas treinta comparaciones. Reducir a la mitad es la imagen espejo de duplicar que ves al convertir números entre bases.

O(n) es lineal: sumar cada elemento o recorrer una lista una vez toca cada elemento exactamente una vez, así que el trabajo sube en línea recta con n. O(n al cuadrado) es cuadrático y suele venir de bucles anidados, como comparar cada par de elementos. Con n de 1000 son un millón de operaciones; con n de 1 000 000 son un billón, y ahí es donde el código cuadrático ingenuo se vuelve inservible sin ruido.

Por qué importa la clase que eliges

La complejidad es lo que separa un prototipo que funciona en tu archivo de prueba de un software que sobrevive a los datos de producción. Ordenar con un algoritmo O(n al cuadrado) parece instantáneo con cien filas y se congela con un millón. Cambiar a una ordenación O(n log n) mantiene la misma tarea por debajo de un segundo. El algoritmo que eliges, no la velocidad de la máquina, fija el techo de cuántos datos puedes manejar.

Dicho esto, Big O es asintótico: describe el comportamiento cuando n tiende a infinito. Para entradas pequeñas, una rutina más simple O(n al cuadrado) puede vencer a una sofisticada O(n log n) con mucha sobrecarga. La regla práctica es conocer la clase de cada operación central y luego optimizar las partes que verán de verdad un n grande, en vez de perseguir constantes en código que solo maneja entradas diminutas.

Preguntas frecuentes

¿Un Big O menor es siempre más rápido?

No para entradas pequeñas. Big O ignora los factores constantes, así que un método O(n log n) con mucha preparación puede perder frente a un simple bucle O(n al cuadrado) cuando n es diminuto. La clase menor gana una vez que la entrada es lo bastante grande.

¿Cuál es la diferencia entre O(log n) y O(n log n)?

O(log n) hace una sola pasada logarítmica, como una única búsqueda binaria. O(n log n) hace una cantidad logarítmica de trabajo por cada uno de los n elementos, que es el costo de algoritmos de ordenación eficientes como el merge sort.

¿Big O cubre también la memoria?

Sí. La misma notación describe la complejidad espacial, cuánta memoria extra necesita un algoritmo al crecer n. Una ordenación in situ puede usar O(1) de espacio extra, mientras que una que copia los datos usa O(n).

¿Por qué ignoramos las constantes y los términos menores?

Porque con n grande el término que crece más rápido domina todo lo demás, y las constantes dependen de un hardware que no controlas. Descartarlos da una comparación portable de cómo escalan los algoritmos, independiente de cualquier máquina.