Notación Big O: Cómo Medir la Eficiencia de un Algoritmo sin Complicaciones

Entiende la notación Big O con ejemplos simples: O(1), O(log n), O(n), O(n log n) y O(n²), y aprende a estimar la eficiencia de tus algoritmos.

Compartir en Linkedin Compartir en WhatsApp

Tiempo estimado de lectura: 7 minutos

Imagen del artículo Notación Big O: Cómo Medir la Eficiencia de un Algoritmo sin Complicaciones

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):

Complejidadn = 10n = 1.000n = 1.000.000
O(1)111
O(log n)~3~10~20
O(n)101.0001.000.000
O(n log n)~33~10.000~20.000.000
O(n²)1001.000.0001.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

  1. Un bucle que recorre los n elementos suele indicar O(n).
  2. Dos bucles anidados sobre los mismos datos suelen indicar O(n²).
  3. Bucles uno detrás de otro se suman: O(n) + O(n) sigue siendo O(n).
  4. Un bucle que divide el problema a la mitad en cada vuelta suele indicar O(log n).
  5. 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.

Qué Es un Motor de Videojuegos y Cómo Funciona el Bucle de Juego

Descubre qué hace un motor de videojuegos, cómo funciona el bucle de juego y qué papel cumplen el renderizado, la física y el delta time.

Claves Primarias y Foráneas: Cómo se Relacionan las Tablas en una Base de Datos

Aprende qué son las claves primarias y foráneas, cómo conectan tablas, qué tipos de relaciones existen y por qué protegen la integridad de tus datos.

Qué Es el DNS: Cómo tu Navegador Encuentra un Sitio Web en Milisegundos

Entiende cómo funciona el sistema de nombres de dominio, qué son los registros A, CNAME y MX, y por qué a veces los cambios tardan.

Cifrado de Extremo a Extremo: Cómo Funciona y Qué Protege Realmente

Explicación sencilla del cifrado de extremo a extremo: claves pública y privada, qué protege, qué no protege y por qué importa.

Memoria RAM y almacenamiento: por qué no son lo mismo

Diferencias entre RAM y disco, qué hace cada uno, qué pasa cuando falta memoria y cuál conviene ampliar primero.

Qué es el DOM y Cómo lo Usa JavaScript para Cambiar una Página Web

Descubre qué es el DOM, cómo el navegador convierte el HTML en un árbol de nodos y cómo JavaScript lo modifica en tiempo real.

La Regla 3-2-1 de las Copias de Seguridad: Cómo Proteger tus Archivos de Verdad

Descubre en qué consiste la regla 3-2-1 de respaldo, los tipos de copia que existen y los errores más comunes al proteger la información.

Diagramas de flujo y pseudocódigo: cómo planificar un programa antes de escribirlo

Aprende a usar diagramas de flujo y pseudocódigo para diseñar algoritmos claros antes de escribir una sola línea de código.