Cómo saber si un algoritmo va a escalar

Un algoritmo puede tardar un milisegundo con diez datos y volverse inutilizable con un millón. Medirlo una vez no alcanza. Lo que importa es cómo crece el trabajo cuando crece la entrada, y eso es lo que intenta capturar la notación Big O.

Qué se cuenta, ya que no son segundos

No contamos segundos porque dependen de la máquina, el lenguaje y lo que esté ejecutándose al mismo tiempo. Contamos operaciones relevantes en función del tamaño de entrada $n$.

const contains = (values: number[], target: number): boolean => {
  for (const value of values) {
    if (value === target) return true;
  }
  return false;
};

En el peor caso, contains mira los $n$ elementos. Si duplicamos la cantidad de datos, duplicamos aproximadamente el trabajo. Decimos que su tiempo crece como $O(n)$.

Por qué sobrevive sólo el término dominante

Supongamos que una cuenta exacta da

Para entradas grandes, $n^2$ domina a $n$ y a la constante. Big O conserva esa forma de crecimiento y descarta coeficientes:

No significa que las constantes nunca importen. Importan al optimizar un sistema real. Significa que una constante no puede salvar un crecimiento peor para siempre: por muy rápido que sea hoy un algoritmo cuadrático, uno lineal termina ganándole cuando $n$ crece.

La escalera de las familias comunes

Las familias más comunes forman una escalera:

La diferencia se vuelve brutal rápido. Con $n=1.000.000$, $\log_2 n$ ronda 20; $n^2$ es un billón. No son optimizaciones pequeñas: son problemas de otra escala.

Un ciclo no es automáticamente O(n)

Un ciclo no implica automáticamente $O(n)$ y dos ciclos no implican automáticamente $O(n^2)$. Hay que mirar cuántas veces corre cada uno.

Dos ciclos consecutivos de $n$ pasos hacen $n+n=2n$, que sigue siendo $O(n)$. Dos ciclos anidados de $n$ pasos hacen $n\cdot n=n^2$. Pero si el índice se duplica en cada vuelta,

for (let step = 1; step < size; step *= 2) {
  visit(step);
}

el ciclo corre sólo $\log_2 n$ veces. La sintaxis se parece; la progresión del índice es la que decide el costo.

De dónde sale un logaritmo

La búsqueda binaria trabaja sobre datos ordenados. En cada comparación descarta la mitad de lo que queda. Después de $k$ pasos quedan $n/2^k$ candidatos. Cuando queda uno,

Esa ecuación explica $O(\log n)$ mejor que memorizarlo. La base del logaritmo no aparece en Big O porque cambiar de base sólo multiplica por una constante.

Antes de anunciar una complejidad, decir qué es n

Antes de anunciar una complejidad hay que decir qué representa $n$. En un grafo suelen importar dos tamaños, vértices $V$ y aristas $E$; un recorrido cuesta $O(V+E)$. En una matriz rectangular importan filas y columnas; recorrerla cuesta $O(f\cdot c)$.

Reducir todo a una sola letra puede esconder el dato que realmente crece. “Es lineal” no alcanza: lineal ¿en usuarios, mensajes, píxeles o conexiones entre nodos?

O, Omega y Theta: tres cosas distintas

Formalmente, $O(g(n))$ es una cota superior: para entradas suficientemente grandes, el costo no crece más rápido que una constante por $g(n)$. $\Omega(g(n))$ es una cota inferior y $\Theta(g(n))$ indica que ambas coinciden.

En conversaciones de programación se usa “es $O(n)$” para decir “crece linealmente”, que formalmente sería $\Theta(n)$. La distinción importa en demostraciones, pero en una entrevista o revisión de código suele importar más declarar el caso analizado y justificar el conteo.

Lo que la notación esconde

Cierre

Big O no adivina rendimiento: elimina soluciones que no pueden escalar. Definí el tamaño de entrada, contá cómo avanza el algoritmo y quedate con el crecimiento dominante. Después medí constantes y hardware. Primero elegís una familia viable; recién entonces optimizás sus detalles.