¿Qué es Big O y por qué es tan importante?

Una herramienta fundamental para analizar la eficiencia de algoritmos y predecir cómo se comportan a gran escala

Cuando pensamos en la calidad de un programa de computadora, a menudo nos enfocamos en su velocidad: ¿cuánto tarda en iniciar Visual Studio Code?, ¿qué tan rápido carga Instagram cuando abres la app?, ¿por qué Netflix reproduce un video al instante mientras que YouTube a veces se queda cargando? Sin embargo, la verdadera medida de un algoritmo eficiente no es solo lo rápido que se ejecuta una vez, sino qué tan bien escala a medida que la cantidad de datos aumenta dramáticamente.

Aquí es donde entra en juego la Notación Big O (O). La Notación Big O es una herramienta fundamental en la informática que nos proporciona un análisis simplificado de la eficiencia de un algoritmo. Nos permite comparar algoritmos y predecir el impacto que tendrá el aumento del tamaño de la entrada (N) en el tiempo de ejecución, sin preocuparnos por los detalles específicos de la máquina.

¿Por Qué No Medimos Simplemente la Velocidad?

En el mundo real, la velocidad de ejecución de un código depende de muchos factores: el tipo de procesador, la memoria caché, el lenguaje de programación, e incluso si otras aplicaciones se están ejecutando simultáneamente.

Para comparar algoritmos de manera justa e independiente de la máquina, necesitamos un marco teórico que nos permita evaluar la eficiencia intrínseca de los algoritmos, ignorando factores externos como el hardware, el sistema operativo o la implementación específica del lenguaje.

Existen varios marcos teóricos para el análisis algorítmico: el Modelo de Máquina de Turing (que se centra en la computabilidad teórica), el Modelo de Circuitos Booleanos (usado en complejidad de circuitos), y el Modelo PRAM (Parallel Random Access Machine, para algoritmos paralelos). Sin embargo, para el análisis práctico de algoritmos secuenciales, utilizamos el Modelo RAM.

El Modelo RAM Simplificado

Este modelo de Máquina de Acceso Aleatorio simplifica la realidad haciendo 3 suposiciones clave:

1. Instrucciones Primitivas: Asume que operaciones aritméticas básicas (sumar, restar, multiplicar, dividir), movimiento de datos (cargar, almacenar, copiar) y estructuras de control (bucles, llamadas a funciones) toman un tiempo constante (una unidad de tiempo).
2. Tiempo de Ejecución: Definimos el tiempo de ejecución como el número de pasos u operaciones primitivas ejecutadas.
3. Tamaño de la Entrada (N): El tiempo de cálculo generalmente crece con el tamaño de la entrada. Por ejemplo, en un algoritmo de ordenamiento, N es la cantidad de elementos a ordenar.

El Foco Asintótico

El objetivo de la notación Big O es observar la eficiencia asintótica del algoritmo. Esto significa que nos interesa principalmente cómo se comporta el tiempo de ejecución cuando el tamaño de la entrada (N) se vuelve extremadamente grande.

Para centrarnos en el crecimiento real y simplificar el análisis, aplicamos dos reglas cruciales:

Regla 1: Descartar Constantes

La notación Big O ignora las constantes.

Consideremos un algoritmo simple que busca un elemento específico en un array:

function buscarElemento(array, elemento) {
  // 1 operación: inicializar i
  // N operaciones: comparar array[i] === elemento
  // N operaciones: incrementar i
  // N operaciones: evaluar condición i < array.length
  // 1 operación: return

  for (let i = 0; i < array.length; i++) {
    if (array[i] === elemento) {
      return i;
    }
  }
  return -1;
}

En el peor caso, este algoritmo ejecuta aproximadamente 3N + 2 operaciones (3N dentro del bucle + 2 operaciones fuera). Sin embargo, en Big O simplificamos esto a O(N), ignorando tanto la constante 3 como el término +2.

¿Por qué? Porque a medida que N se vuelve muy grande (1 millón, 10 millones), la diferencia entre 3N y N se vuelve insignificante en términos de tasa de crecimiento. Big O se enfoca en medir cómo escalan los algoritmos, por lo que prioriza la tasa de crecimiento por encima de los detalles específicos de implementación.

Regla 2: Descartar Términos de Orden Inferior

En una función que describe el tiempo de ejecución de un algoritmo, los términos que crecen más lentamente se vuelven insignificantes a medida que N aumenta.

Imaginemos un algoritmo que encuentra todos los pares de elementos duplicados en un array:

function encontrarParesDuplicados(array) {
  // Bucle exterior: N operaciones
  for (let i = 0; i < array.length; i++) {
    // Bucle interior: N operaciones por cada iteración del exterior
    for (let j = i + 1; j < array.length; j++) {
      if (array[i] === array[j]) {
        console.log(`Duplicado encontrado: ${array[i]}`);
      }
    }
  }

  // Operaciones adicionales: ordenar el array al final
  array.sort(); // N log N operaciones

  // Operaciones finales
  console.log("Búsqueda completada"); // 1 operación
}

Analizando las operaciones:

• Bucles anidados: N² operaciones (dominante)
• Ordenamiento: N log N operaciones (O(N log N) para algoritmos eficientes como merge sort, lo veremos en detalle en posts futuros)
• Operaciones constantes: 1 operación

La función completa sería: T(N) = N² + N log N + 1

Pero observemos qué sucede con valores grandes:

• Si N = 1,000: N² = 1,000,000 vs N log N ≈ 10,000 vs 1 = 1
  • Total: 1,010,001 operaciones (N² contribuye 99.01%)
• Si N = 100,000: N² = 10,000,000,000 vs N log N ≈ 1,660,000 vs 1 = 1
  • Total: 10,001,660,001 operaciones (N² contribuye 99.98%)

El término N² domina completamente, por lo que simplificamos a O(N²). Los términos de menor orden se vuelven despreciables ante el crecimiento cuadrático.

El Énfasis en el Peor Caso

Cuando analizamos algoritmos, generalmente nos centramos en el peor caso.

El peor caso ocurre cuando la entrada hace que el algoritmo realice la mayor cantidad de pasos. Por ejemplo, en un algoritmo de búsqueda lineal en un array, el peor caso es que el elemento que buscamos esté al final del array o no exista en absoluto, obligando al algoritmo a buscar en cada elemento.

El peor caso es crucial porque nos da un límite superior. Saber que un algoritmo nunca tardará más de cierto tiempo nos proporciona una garantía de rendimiento, lo cual es mucho más útil que el mejor caso (que a menudo es irrelevante) o el caso promedio (que puede ser difícil de calcular).

Las Notaciones Asintóticas: O, Ω, y Θ

Desde el punto de vista académico y matemático, existen tres notaciones formales para describir la eficiencia de los algoritmos. La academia utiliza estos conceptos para establecer límites precisos sobre el comportamiento de las funciones que describen el tiempo de ejecución:

A. Big O (O): El Límite Superior

Big O (O) se utiliza para establecer solo un límite superior. Decimos que una función de tiempo f(N) es O(g(N)) (se lee: f es "big oh" de g) si la tasa de crecimiento de f(N) es a lo sumo tan rápida como la de g(N).

Definición formal: f(N) = O(g(N)) si existen constantes positivas C y N₀ tales que 0 ≤ f(N) ≤ C · g(N) para todo N ≥ N₀.

Ejemplo práctico: Es como decir "el viaje en auto a la playa toma a lo sumo 3 horas". Puede que llegues en 2 horas si no hay tráfico, pero nunca tardará más de 3 horas. Big O nos da esa garantía de límite superior.

• Aplicación: En términos estrictamente académicos, Big O establece un límite superior, pero como veremos más adelante, en la industria usamos este término de manera más amplia.

B. Big Omega (Ω): El Límite Inferior

Big Omega (Ω) se utiliza para establecer solo un límite inferior. Decimos que f(N) es Ω(g(N)) si la tasa de crecimiento de f(N) es al menos tan rápida como la de g(N).

Definición formal: f(N) = Ω(g(N)) si existen constantes positivas C y N₀ tales que 0 ≤ C · g(N) ≤ f(N) para todo N ≥ N₀.

Ejemplo práctico: Es como decir "necesito al menos 1 hora para preparar la cena". Puede que tome 1 hora o más (si es una receta compleja), pero nunca menos de 1 hora. Big Omega nos asegura el tiempo mínimo requerido.

C. Big Theta (Θ): El Límite Ajustado

Big Theta (Θ) proporciona un límite superior e inferior (un límite asintóticamente ajustado).

Definición formal: f(N) = Θ(g(N)) si se cumplen simultáneamente las condiciones de Big O y Big Omega: existen constantes positivas C₁, C₂ y N₀ tales que C₁ · g(N) ≤ f(N) ≤ C₂ · g(N) para todo N ≥ N₀.

Ejemplo práctico: Es como decir "mi rutina matutina toma exactamente entre 45 y 60 minutos". Tenemos tanto un límite inferior (nunca menos de 45 min) como superior (nunca más de 60 min). Big Theta nos da el rango exacto de crecimiento.

• Significado: Si decimos que el tiempo de ejecución de un programa es Θ(N²), estamos afirmando que su parte dominante es exactamente el componente N².

Perspectiva Industrial vs Académica

Existen diferencias importantes entre cómo la academia define la eficiencia algorítmica y cómo la industria del software la interpreta en la práctica. Estas diferencias reflejan las distintas necesidades: la academia busca precisión matemática, mientras que la industria busca herramientas prácticas para tomar decisiones de diseño.

Dispersando el Costo (Amortization)

Aunque la definición académica de Big O se centra en el peor caso, en la industria a menudo "amortizamos" ese peor caso distribuyendo su costo a lo largo de múltiples operaciones. El análisis amortizado no hace que el algoritmo corra más rápido, sino que es una forma de contabilidad que ayuda a demostrar que la eficiencia promedio del algoritmo es mejor de lo que sugiere el peor caso individual.

La amortización implica tomar una gran cantidad de costo (que ocurre raramente, quizás al principio) y dispersarla a lo largo del tiempo o un número de operaciones.

Ejemplo de Dunkin Donuts: Si cuesta $1 millón abrir una franquicia (costo inicial) y $1 hacer cada dona:

• La primera dona cuesta $1,000,001.
• Pero si asumimos que haremos 1 millón de donas, podemos dispersar el costo inicial de $1 millón entre todas ellas. El costo amortizado es entonces de $1 (costo real) + $1 (parte de la tarifa inicial), haciendo que cada dona cueste $2 en promedio.

"Big O" en la Industria

Cuando los desarrolladores hablan de "Big O", el concepto que manejan está más cercano a la definición académica de Big Theta (Θ) que a la definición estricta de Big O. Cuando decimos que un algoritmo es O(N²), típicamente queremos expresar que su complejidad es cuadrática, no solo que tiene un límite superior cuadrático.

Ejemplo: Si un desarrollador dice "QuickSort es O(N log N)", realmente está comunicando que QuickSort tiene una complejidad típica de N log N (más cercano a Θ(N log N)). QuickSort es un algoritmo de ordenamiento que funciona dividiendo el array en partes más pequeñas de manera recursiva. En la mayoría de los casos, divide eficientemente los datos (log N divisiones) y procesa cada elemento una vez (N operaciones), resultando en N log N operaciones totales.

Sin embargo, académicamente sería más preciso decir que QuickSort es O(N²) en el peor caso (cuando los datos están ordenados de cierta manera que hace que las divisiones sean muy desbalanceadas, procesando casi todos los elementos en cada nivel), pero Θ(N log N) en el caso promedio. En la práctica industrial, usamos "O(N log N)" para referirnos a su comportamiento esperado, ignorando el peor caso poco común.

Jerarquía de Complejidades Comunes

La eficiencia de un algoritmo se clasifica según su orden de crecimiento. Aquí se presentan los más comunes, ordenados de más rápido/más eficiente a más lento/menos eficiente:

Ejemplo Práctico de Crecimiento

Imaginemos que duplicamos el tamaño de nuestra entrada (N):

• O(1): El tiempo no cambia.
• O(N): El tiempo se duplica.
• O(N²): El tiempo se cuadruplica (es proporcional al cuadrado de los datos).

Por ejemplo, en un Bubble Sort con 10,000 elementos tardó 362 ms, pero con 20,000 elementos tardó 1612 ms (aproximadamente 4 veces más), demostrando que el orden N² debe evitarse.

Nota sobre Logaritmos

Si ves una complejidad como O(N log N), no te preocupes por la base del logaritmo (si es log₁₀, log₂, o ln). En la notación Big O, la base del logaritmo no importa, ya que las funciones logarítmicas con bases diferentes son asintóticamente iguales (se relacionan por una constante), y las constantes se ignoran.

Conclusión y Referencias

La Notación Big O (O) es la herramienta fundamental para cualquier desarrollador que busca comprender y diseñar algoritmos que sean escalables. Al descartar constantes y centrarnos en el término de crecimiento dominante (como N² en lugar de 45N³ + 20N² + 19) y priorizar el peor caso, logramos medir la eficiencia asintótica, es decir, qué tan bien un algoritmo se escala a medida que el tamaño de la entrada (N) se vuelve extremadamente grande. Esta perspectiva teórica nos da garantías de rendimiento a largo plazo, sin que la velocidad se vea alterada por los detalles específicos de la máquina o el lenguaje de programación que utilicemos.

Si te interesa ahondar más en estos temas de análisis algorítmico, límites asintóticos (Ω, Θ) y eficiencia, puedes consultar las siguientes referencias que sirvieron de base para este artículo:

• Harvard CS50 – Asymptotic Notation (video)
• Big O Notations (general quick tutorial) (video)
• Big O Notation (and Omega and Theta) – best mathematical explanation (video)
• Skiena (video)
• UC Berkeley Big O (video)
• Amortized Analysis (video)
• Computational Complexity: Section 1
• Computational Complexity: Section 2
• Big-O Algorithm Complexity Cheat Sheet
• [Review] Analyzing Algorithms (playlist) in 18 minutes (video)