2 - Concepto de notación Big-O

Esta lección profundiza en la notación Big-O, explicando cómo se formalizan las cotas de crecimiento, por qué descartamos constantes y cómo comparar algoritmos implementados en C.

2.1 ¿Qué representa Big-O?

Big-O sirve para decir qué tan rápido aumenta el costo de un algoritmo cuando crece el tamaño de los datos. No mide tiempo exacto en segundos, sino la velocidad de crecimiento en el largo plazo. Por ejemplo, afirmar que un recorrido de un array es O(n) indica que el trabajo crece en proporción directa a la cantidad de elementos.

La definición formal usa cotas. Decimos que f(n) = O(g(n)) si existen constantes positivas c y n0 tales que f(n) ≤ c × g(n) para todo n ≥ n0. En palabras: a partir de cierto tamaño, la función f(n) nunca crece más rápido que g(n) multiplicada por una constante.

Este enfoque asintótico nos permite comparar algoritmos sin depender de un hardware específico ni de microdetalles de implementación; nos quedamos con la tendencia general de crecimiento.

2.2 Descartar constantes y términos menores

Para centrar el análisis en el crecimiento dominante, ignoramos constantes y términos de menor orden:

• 5n + 20 se simplifica a O(n), porque el coeficiente 5 y el término 20 no cambian la tendencia.
• n^2 + 3n + 10 se reduce a O(n^2); el término cuadrático eclipsa al resto para valores grandes de n.
• Al multiplicar por una constante de tiempo (latencia de una lectura, por ejemplo), la forma de la función no cambia: sigue siendo el mismo Big-O.

Esta simplificación permite razonar sobre escalabilidad sin depender de detalles de implementación o micro-optimizaciones.

2.3 ¿Cómo comparar algoritmos?

El orden de crecimiento ofrece una guía directa para escoger entre alternativas:

• Primero el orden: preferir O(n) frente a O(n^2) cuando el tamaño puede crecer.
• Luego las constantes: si dos opciones tienen el mismo Big-O, elegir la que realiza menos trabajo constante o que aproveche mejor la memoria.
• Contexto de uso: un algoritmo O(n log n) puede ser mejor que uno O(n) si el segundo usa demasiada memoria o no escala en caches.

Para comparar implementaciones reales en C, combina el análisis Big-O con mediciones: tiempos de ejecución en distintos n y contadores de memoria.

2.4 Diferencia entre Big-O, Big-Ω y Big-Θ

La notación asintótica tiene tres variantes principales:

• Big-O: cota superior. Garantiza que el algoritmo no crecerá más rápido que g(n) a partir de cierto punto.
• Big-Ω: cota inferior. Indica que el algoritmo al menos crecerá tan rápido como g(n).
• Big-Θ: cota ajustada. Se cumple cuando tanto la cota superior como la inferior coinciden; captura el crecimiento real asintótico.

En la práctica, describir un algoritmo con Big-Θ es más preciso, pero Big-O sigue siendo la notación más usada en documentación y entrevistas técnicas.

2.5 Orden de crecimiento

Ordenar las complejidades comunes ayuda a visualizar cómo se comportan al aumentar n:

• O(1): constante. Acceso directo a un array o a una posición de memoria.
• O(log n): logarítmica. Búsqueda binaria en un array ordenado.
• O(n): lineal. Recorrer una lista enlazada de principio a fin.
• O(n log n): lineal-logarítmica. Ordenamientos eficientes basados en comparaciones.
• O(n^2): cuadrática. Bucles anidados que comparan cada par de elementos.
• O(2^n) y O(n!): exponencial y factorial. Algoritmos que exploran todas las combinaciones o permutaciones.