Notación Big O — Complejidad temporal explicada de forma simple

La notación Big O te dice qué tan rápido puede crecer el tiempo de ejecución o el uso de memoria de un algoritmo a medida que crece el tamaño de la entrada. Si te preguntas “¿qué pasa cuando el problema se hace mucho más grande?”, Big O es la forma estándar de responderlo.

Por eso se dice que la búsqueda lineal es $O(n)$ y la búsqueda binaria es $O(\log n)$. El objetivo no es predecir milisegundos exactos en una sola máquina. El objetivo es comparar patrones de crecimiento.

Qué significa Big O

Si un algoritmo tarda $T(n)$ en una entrada de tamaño $n$, entonces

$$T(n) = O(f(n))$$

significa que existen constantes $C > 0$ y $n_0$ tales que

$$T(n) \le C f(n) \quad \text{para todo } n \ge n_0$$

Esto dice que Big O es una afirmación de cota superior sobre el crecimiento para entradas suficientemente grandes.

En lenguaje sencillo: una vez que $n$ es lo bastante grande, el tiempo de ejecución no crece más rápido que un múltiplo constante de $f(n)$.

Por qué Big O es útil

Big O ofrece una forma independiente de la máquina para comparar algoritmos. Un programa puede ejecutarse más rápido en un portátil que en otro, pero la tendencia de crecimiento sigue importando.

Esa tendencia importa más cuando el tamaño de la entrada cambia mucho. Un algoritmo que funciona bien para $100$ elementos puede volverse impracticable para $10^6$ elementos si su tasa de crecimiento es mala.

Complejidades temporales comunes de un vistazo

• $O(1)$: el trabajo se mantiene acotado a medida que crece $n$.
• $O(\log n)$: el trabajo crece lentamente, a menudo cuando el tamaño del problema se reduce repetidamente.
• $O(n)$: el trabajo crece aproximadamente en proporción al tamaño de la entrada.
• $O(n \log n)$: un poco más que lineal, común en algoritmos de ordenación eficientes.
• $O(n^2)$: el trabajo crece como el cuadrado del tamaño de la entrada, a menudo por bucles anidados sobre los mismos datos.

Estas etiquetas comparan crecimiento, no velocidad exacta. Un algoritmo $O(n)$ puede seguir siendo más lento que uno $O(n^2)$ para entradas pequeñas si sus factores constantes son grandes.

Ejemplo resuelto: por qué la búsqueda lineal es $O(n)$

Supón que recorres una lista de izquierda a derecha buscando un valor objetivo. En el peor caso, el valor no está o está al final de todo, así que puede que necesites revisar cada elemento una vez.

Si la lista tiene $n$ elementos, el número de comprobaciones puede ser como máximo $n$. Por eso el tiempo en el peor caso es

$$O(n)$$

La idea clave es simple: si el tamaño de la lista se duplica, el número máximo de comprobaciones también puede duplicarse aproximadamente. Ese es el patrón que Big O captura.

Lo que Big O deja fuera

Big O ignora intencionalmente los factores constantes y los términos de menor orden al comparar el crecimiento para entradas grandes.

Por ejemplo, si

$$T(n) = 3n + 2$$

entonces $T(n)$ sigue siendo $O(n)$. La constante $3$ y el $2$ adicional importan para el tiempo exacto, pero no cambian el patrón principal de crecimiento.

Eso no significa que las constantes nunca importen en la práctica. Significa que Big O responde a una pregunta más concreta: cómo escala el coste cuando $n$ se hace grande.

Errores comunes con Big O

Error 1: Tratar Big O como si fuera el tiempo exacto de ejecución

$O(n)$ no significa que el tiempo de ejecución sea exactamente $n$ pasos. Significa que el crecimiento está acotado superiormente por un múltiplo constante de $n$ una vez que $n$ es lo bastante grande.

Error 2: Olvidar la condición de $n$ grande

La definición formal solo necesita cumplirse para todo $n \ge n_0$. Big O trata del comportamiento asintótico, no de cada entrada pequeña.

Error 3: Suponer que Big O siempre significa tiempo típico de ejecución

En discusiones sobre algoritmos, Big O suele describir el tiempo en el peor caso, pero eso es una convención ligada al contexto. La complejidad en caso promedio y en el mejor caso son preguntas distintas y deben etiquetarse con claridad.

Error 4: Comparar algoritmos solo por Big O

Big O es importante, pero el uso de memoria, el coste de implementación y los factores constantes también pueden importar mucho en sistemas reales.

Dónde aparece la notación Big O

Big O aparece en informática, matemáticas discretas y análisis de rendimiento. Es especialmente útil al comparar algoritmos de búsqueda, ordenación, recorrido de grafos y programación dinámica.

De forma más general, se usa siempre que te importa cómo escala un proceso, y no solo cómo se comporta en un tamaño fijo.

Prueba un ejemplo similar

Toma un bucle anidado sencillo que recorra una cuadrícula de $n \times n$. Cuenta cuántas veces se ejecuta la acción interna. Si el trabajo total crece como $n^2$, tendrás un ejemplo concreto de por qué los bucles repetidos sobre los mismos datos suelen llevar a un comportamiento $O(n^2)$.