Big O

Resumen

Big O es una notación matemática que describe la tasa de crecimiento de una función. En ciencias de la computación se usa para expresar cómo escala el tiempo de ejecución o el uso de memoria de un algoritmo cuando la entrada se hace más grande. No mide segundos ni bytes: mide la forma de la curva.

Importa porque elegir un algoritmo sin entender su Big O es como elegir una ruta sin mirar el mapa. Dos algoritmos que resuelven el mismo problema pueden comportarse igual con 10 elementos y ser órdenes de magnitud distintos con 10 millones. Big O te dice cuál va a seguir siendo usable cuando los datos crezcan.

La notación responde una sola pregunta: «si duplico el tamaño de la entrada, ¿cómo cambia el costo del algoritmo?». Con esa respuesta podés comparar opciones, justificar decisiones de diseño y detectar cuellos de botella antes de que aparezcan en producción.

Alcance y supuestos

Este paquete cubre Big O como herramienta práctica para desarrolladores: las clases de complejidad más comunes, cómo leer complejidad desde código con reglas simples, la diferencia entre tiempo y espacio, y cómo comparar dos algoritmos usando Big O. También menciona brevemente las otras notaciones asintóticas —Omega (Ω) y Theta (Θ)— para que sepas que existen.

No cubre demostraciones formales con límites y constantes, análisis amortizado, complejidad promedio versus peor caso en profundidad, ni teoría de la complejidad (P, NP, NP-completo). No es un curso de algoritmos: es la herramienta de razonamiento que usás antes de entrar a ese curso.

Asume que podés leer código básico (bucles, condicionales, llamadas a funciones) en cualquier lenguaje, y que entendés estructuras de datos elementales como arrays, listas y mapas hash a nivel conceptual.

Modelo mental

Imaginá que estás en la caja de un supermercado. Con una persona, el cajero tarda 30 segundos. Con dos personas, tarda 60 segundos. Con n personas, tarda 30 × n segundos. Duplicar la fila duplica el tiempo. Eso es O(n).

Ahora pensá en ordenar una pila de documentos por fecha. Con pocos papeles los ordenás a mano rápido. Pero cada papel nuevo tenés que compararlo con todos los demás para encontrar su lugar. Si duplicás la pila, el trabajo no se duplica: se cuadruplica aproximadamente. Eso es O(n²).

Big O separa lo que depende del tamaño de la entrada de lo que no. Las constantes —los 30 segundos del cajero por persona— no aparecen en la notación. O(2n) es lo mismo que O(n) porque ambas crecen linealmente. Lo que importa es la forma de la curva, no su altura exacta.

La notación también ignora los términos que crecen más lento que el dominante. Si un algoritmo tarda n² + n + 5 pasos, Big O dice O(n²) porque para n grande, el término n² aplasta a n y a 5. Esa simplificación es la que permite comparar algoritmos sin perderse en detalles.

Uso práctico

Usá Big O cuando necesitás predecir cómo va a comportarse un algoritmo con datos reales, no solo con el caso de prueba de 10 elementos:

• ✅ Comparar dos enfoques para el mismo problema antes de implementar.
• ✅ Justificar por qué un endpoint debe usar un índice en vez de un barrido lineal.
• ✅ Detectar que un for dentro de otro for sobre la misma estructura escala mal antes de que los usuarios lo noten.
• ❌ Medir el rendimiento exacto en milisegundos de una función: para eso existen benchmarks.
• ❌ Predecir cuál es más rápido para n pequeño (menos de ~50 elementos): ahí las constantes que Big O descarta sí importan.

Las clases de complejidad más comunes

Estas son las curvas que vas a encontrar en la práctica, ordenadas de mejor a peor escalabilidad:

| Notación | Nombre | Duplicar n hace que el costo... | Ejemplo típico | |---|---|---|---| | O(1) | Constante | No cambia | Acceso a un array por índice | | O(log n) | Logarítmica | Aumenta una unidad | Búsqueda binaria | | O(n) | Lineal | Se duplica | Recorrer un array de punta a punta | | O(n log n) | Linealítmica | Algo más que duplicar | Ordenamiento eficiente (mergesort, quicksort) | | O(n²) | Cuadrática | Se cuadruplica | Doble bucle anidado | | O(2ⁿ) | Exponencial | Se eleva al cuadrado | Fuerza bruta sobre subconjuntos |

O(1) y O(log n) son el territorio seguro: el algoritmo escala bien incluso con millones de elementos. O(n) y O(n log n) son aceptables para la mayoría de aplicaciones. O(n²) empieza a doler con miles de elementos. O(2ⁿ) se vuelve impracticable rápidamente: con n = 30, 2³⁰ ya supera los mil millones.

Reglas prácticas para leer Big O desde código

No necesitás demostraciones formales para estimar complejidad. Estas reglas cubren el 90% del código que vas a escribir o revisar:

Regla 1: un bucle simple que recorre n elementos es O(n).

function sum(arr: number[]) {
  let total = 0;
  for (const x of arr) {  // n iteraciones
    total += x;           // O(1) por iteración
  }
  return total;
}
// Complejidad: O(n)

Regla 2: dos bucles anidados sobre la misma entrada son O(n²).

function hasDuplicate(arr: number[]) {
  for (let i = 0; i < arr.length; i++) {       // n iteraciones
    for (let j = i + 1; j < arr.length; j++) {  // hasta n por cada i
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}
// Complejidad: O(n²)

Regla 3: operaciones sobre estructuras de datos tienen su propia complejidad. Conocer las complejidades de las operaciones básicas evita bugs de rendimiento. Por ejemplo, buscar en un array sin ordenar es O(n), pero en un hash map es O(1) promedio:

// O(n): busca secuencial
function findUser(users: User[], id: number) {
  return users.find(u => u.id === id);
}

// O(1) promedio: acceso por clave
function findUser(usersById: Map<number, User>, id: number) {
  return usersById.get(id);
}

Regla 4: bucles consecutivos se suman, pero el dominante gana.

function process(arr: number[]) {
  for (const x of arr) { /* ... */ }  // O(n)
  for (const x of arr) { /* ... */ }  // O(n)
  // O(n) + O(n) = O(2n) → O(n)
}

Regla 5: un bucle que reduce el espacio de búsqueda a la mitad en cada iteración es O(log n).

function binarySearch(arr: number[], target: number) {
  let low = 0, high = arr.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}
// Cada iteración parte el rango a la mitad → O(log n)

Espacio: la otra mitad de la historia

Big O también se aplica a la memoria. Un algoritmo que crea una copia del array de entrada es O(n) en espacio adicional. Uno que solo usa variables sueltas es O(1) en espacio.

// O(1) espacio extra: opera sobre el array original
function sumInPlace(arr: number[]) {
  let total = 0;
  for (const x of arr) total += x;
  return total;
}

// O(n) espacio extra: crea un nuevo array
function doubleValues(arr: number[]) {
  return arr.map(x => x * 2);
}

En aplicaciones web y móviles la memoria puede ser más escasa que el tiempo de CPU. Un algoritmo O(n) en tiempo pero O(n) en espacio puede ser peor que uno O(n²) en tiempo pero O(1) en espacio, dependiendo del contexto.

Otras notaciones: Omega y Theta

Big O (O) describe el peor caso —una cota superior—. Es la más usada porque responde «en el peor escenario, ¿qué tan mal puede ser esto?».

Omega (Ω) describe el mejor caso —una cota inferior—: «en el mejor escenario, ¿qué tan rápido puede ser?». Por ejemplo, buscar en un array: Ω(1) si el elemento está en la primera posición.

Theta (Θ) describe el caso ajustado —cuando la cota superior y la inferior coinciden—: «el crecimiento real es exactamente esta curva». Por ejemplo, sumar todos los elementos de un array es Θ(n) porque tanto el mejor como el peor caso recorren todo el array.

En la práctica diaria alcanza con Big O. Omega y Theta aparecen en bibliografía académica y en análisis más finos de algoritmos específicos.

Ejemplo trabajado: comparar dos enfoques para encontrar duplicados

Un sistema necesita detectar si una lista de IDs de transacciones contiene duplicados. Recibe arrays de entre 100 y 100 000 elementos. El equipo propone dos enfoques:

Enfoque A: doble bucle

function hasDuplicateA(ids: string[]) {
  for (let i = 0; i < ids.length; i++) {
    for (let j = i + 1; j < ids.length; j++) {
      if (ids[i] === ids[j]) return true;
    }
  }
  return false;
}
// Tiempo: O(n²)
// Espacio: O(1)

Enfoque B: usar un Set

function hasDuplicateB(ids: string[]) {
  const seen = new Set<string>();
  for (const id of ids) {
    if (seen.has(id)) return true;
    seen.add(id);
  }
  return false;
}
// Tiempo: O(n)
// Espacio: O(n)

Big O da el criterio para elegir:

| n | Enfoque A (O(n²)) | Enfoque B (O(n)) | |---|---|---| | 100 | ~5 000 operaciones | ~100 operaciones | | 1 000 | ~500 000 operaciones | ~1 000 operaciones | | 100 000 | ~5 000 000 000 operaciones | ~100 000 operaciones |

Con 100 elementos, ambos son instantáneos. Con 100 000, el enfoque A tarda segundos; el B, milisegundos. La diferencia no es de optimización prematura: es de arquitectura. El enfoque B paga con O(n) de memoria adicional, lo cual es aceptable para IDs de transacciones en la mayoría de los servidores modernos. Si la memoria fuera extremadamente limitada, se podría explorar un enfoque que ordene el array primero —O(n log n) tiempo, O(1) espacio— como término medio.

Antes de decidir basándote solo en Big O, preguntate:

1. ¿Cuál es el tamaño máximo realista de la entrada en producción?
2. ¿El algoritmo se ejecuta una vez por request, por usuario o por lote nocturno?
3. ¿El cuello de botella real es CPU, memoria, red o disco?
4. ¿La complejidad que estás estimando es la del peor caso o la del caso promedio?

Big O orienta la decisión, pero no reemplaza medir en producción. Un O(n²) que solo se ejecuta una vez al día sobre 50 elementos es irrelevante. Un O(n) que se ejecuta por cada request sobre arrays de 10 millones de elementos necesita más análisis.

Evidencia

• Wikipedia, Big O notation presenta la definición formal, las clases de complejidad estándar y las notaciones relacionadas Omega y Theta.
• Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms (CLRS) es el texto canónico sobre análisis de algoritmos, con capítulos dedicados a notación asintótica, recurrencias y complejidad.
• MIT OpenCourseWare, 6.006 Introduction to Algorithms cubre análisis asintótico desde la primera unidad, con ejemplos de cómo leer complejidad desde código y comparar algoritmos.