Dos programas pueden resolver el mismo problema y, aun así, uno tardar milisegundos y el otro horas. La diferencia rara vez está en el lenguaje o en el ordenador: casi siempre está en el algoritmo. Para comparar algoritmos de forma objetiva, los programadores usan una herramienta llamada notación Big O. En este artículo aprenderás qué significa, cuáles son las complejidades más comunes, cómo reconocerlas en el código y por qué este conocimiento es tan valorado en entrevistas técnicas y en el trabajo diario.
Qué es la notación Big O
La notación Big O describe cómo crece el tiempo de ejecución (o el uso de memoria) de un algoritmo a medida que aumenta el tamaño de la entrada, que se representa con la letra n. No mide segundos exactos, sino la tendencia de crecimiento. La pregunta que responde es: si duplico la cantidad de datos, ¿qué pasa con el trabajo que hace el algoritmo?
Por convención, Big O suele usarse para describir el peor caso, es decir, la situación en la que el algoritmo tiene que hacer más trabajo. Así obtenemos un límite superior: sabemos que, como máximo, el algoritmo crecerá a ese ritmo.
Dos reglas para simplificar
Como Big O se interesa por el comportamiento con entradas grandes, se aplican dos simplificaciones:
- Se ignoran las constantes. Un algoritmo que hace 3n operaciones y otro que hace n operaciones son ambos O(n). Con datos enormes, lo que importa es que los dos crecen de forma lineal.
- Se conserva solo el término dominante. Si un algoritmo hace n² + 5n + 10 operaciones, se escribe O(n²), porque cuando n es grande el término n² es mucho mayor que los demás.
Las complejidades más comunes
O(1): tiempo constante
El trabajo no depende del tamaño de la entrada. Acceder a un elemento de un arreglo por su índice, por ejemplo lista[5], cuesta lo mismo si la lista tiene diez o diez millones de elementos.
O(log n): tiempo logarítmico
En cada paso, el problema se reduce a la mitad. El ejemplo clásico es la búsqueda binaria en una lista ordenada: se mira el elemento del medio, se descarta la mitad que no puede contener el valor buscado y se repite. Con mil elementos bastan unas 10 comparaciones; con un millón, unas 20.
O(n): tiempo lineal
El trabajo crece en proporción directa a la entrada. Recorrer una lista para encontrar el valor máximo o buscar un elemento en una lista desordenada son operaciones lineales: si la lista se duplica, el tiempo también.
O(n log n): tiempo linealítmico
Es la complejidad típica de los algoritmos de ordenamiento eficientes, como merge sort, y del caso promedio de quicksort. Crece un poco más rápido que O(n), pero mucho más despacio que O(n²).
O(n²): tiempo cuadrático
Aparece con frecuencia cuando hay dos bucles anidados que recorren la misma colección, como al comparar cada elemento con todos los demás. Los ordenamientos simples, como burbuja, selección e inserción, son O(n²) en el peor caso.
O(2ⁿ): tiempo exponencial
El trabajo se duplica con cada elemento adicional. Probar todos los subconjuntos posibles de un conjunto es un ejemplo. Estos algoritmos se vuelven inviables muy rápido, incluso con entradas modestas.
Comparando el crecimiento
La siguiente tabla muestra, de forma aproximada, cuántas operaciones implica cada complejidad para distintos tamaños de entrada (con logaritmo en base 2):
| Complejidad | n = 10 | n = 1.000 | n = 1.000.000 |
|---|---|---|---|
| O(1) | 1 | 1 | 1 |
| O(log n) | ~3 | ~10 | ~20 |
| O(n) | 10 | 1.000 | 1.000.000 |
| O(n log n) | ~33 | ~10.000 | ~20.000.000 |
| O(n²) | 100 | 1.000.000 | 1.000.000.000.000 |
Observa la última fila: con un millón de elementos, un algoritmo cuadrático necesitaría un billón de operaciones, mientras que uno O(n log n) necesitaría unos veinte millones. Esa es la diferencia entre una respuesta inmediata y un programa que parece colgado.
Cómo reconocer la complejidad en el código
- Un bucle que recorre los n elementos suele indicar O(n).
- Dos bucles anidados sobre los mismos datos suelen indicar O(n²).
- Bucles uno detrás de otro se suman: O(n) + O(n) sigue siendo O(n).
- Un bucle que divide el problema a la mitad en cada vuelta suele indicar O(log n).
- Llamadas a funciones de biblioteca también cuentan: ordenar una lista dentro de un bucle puede multiplicar la complejidad.
Un ejemplo práctico: para comprobar si una lista tiene elementos repetidos, puedes comparar cada par de elementos con dos bucles anidados, lo que da O(n²). Otra opción es recorrer la lista una vez guardando lo visto en un conjunto (set), cuya búsqueda es O(1) en promedio. El resultado es O(n) en tiempo, a cambio de usar O(n) de memoria adicional.
Tiempo y memoria: un equilibrio
El ejemplo anterior muestra algo importante: Big O no se aplica solo al tiempo, sino también al espacio en memoria. Muchas optimizaciones consisten en gastar más memoria para ahorrar tiempo, o al revés. Elegir bien depende del contexto: un sistema embebido con poca memoria y un servidor potente pueden preferir soluciones distintas.
También conviene recordar que Big O describe el comportamiento con entradas grandes. Para listas pequeñas, un algoritmo O(n²) sencillo puede ser incluso más rápido en la práctica que uno sofisticado, porque las constantes que Big O ignora sí influyen cuando n es pequeño.
Conclusión
La notación Big O es un lenguaje común para hablar de eficiencia. Saber distinguir entre O(1), O(log n), O(n), O(n log n) y O(n²) te permite anticipar si una solución aguantará cuando los datos crezcan y elegir estructuras y algoritmos adecuados. No hace falta memorizar fórmulas complejas: basta con observar cómo se repite el trabajo en el código. Si quieres reforzar estas bases, explora los cursos gratuitos de lógica de programación y algoritmos disponibles en Cursa.







