Una introducción visual a la notación Big O

(samwho.dev)

2 puntos por GN⁺ 2025-08-26 | 1 comentarios | Compartir por WhatsApp

La notación Big O expresa el rendimiento de una función como su patrón de crecimiento según cambia el tamaño de la entrada
El artículo explica, con ejemplos, los casos más representativos de Big O: constante, logarítmico, lineal y cuadrático
La complejidad temporal varía según la estructura de datos y el algoritmo, y se nota en tareas como ordenar o buscar en arreglos
Para mejorar el rendimiento real del código, lo más importante es elegir la estructura de datos adecuada y eliminar operaciones innecesarias dentro de los bucles
Big O siempre representa de la forma más simplificada posible la relación entre la entrada y el tiempo de ejecución, y al optimizar el rendimiento es importante medir el código directamente

Descripción general de la notación Big O

La notación Big O es una forma de describir el patrón de crecimiento del tiempo de ejecución según el tamaño de la entrada (n), en lugar de medir el tiempo directamente
Clasifica el tiempo de ejecución de una función según la entrada, y por lo general se analizan formas como constante (O(1)), logarítmica (O(log n)), lineal (O(n)) y cuadrática (O(n²))
Este artículo lo explica con conceptos, ejemplos visuales y ejemplos de código reales para que incluso principiantes puedan entender cada caso

Iteración y algoritmos lineales

La función sum(n) es un ejemplo de una estructura iterativa que suma de 1 a n, y a medida que crece el valor de entrada n, el tiempo de ejecución también aumenta en proporción directa
En la práctica, sum(1e9) tarda alrededor de 1 segundo y sum(2e9) unos 2 segundos, por lo que el tiempo de reloj (wall-clock time) crece con un patrón O(n)
La complejidad temporal es la relación entre la entrada de una función y su tiempo de ejecución, y se expresa con la notación Big O (O(n) — proporcional a n)
En lugar de iterar, usar la fórmula matemática sum(n) = (n*(n+1))/2 hace que el tiempo de ejecución sea constante e independiente del valor de entrada n
A este tipo de función se le llama complejidad temporal constante O(1), y su rasgo principal es que el tiempo de ejecución no crece cuando cambia la entrada

Sintaxis de la notación Big O

La O de Big O viene de “Order” (orden de crecimiento) y solo indica la forma del crecimiento en sí
No representa el valor absoluto del tiempo de ejecución, sino solo el 'patrón' de crecimiento respecto a la entrada de manera concisa
Por ejemplo, aunque una función sea O(n), no se escribe de forma complicada como 'O(2n)' o 'O(n+1)', sino que se elige solo el término más simple

Reducir el tiempo usando la estructura de la entrada

Como en el ejemplo de la fórmula de sum(n), mejorar el algoritmo puede cambiar la complejidad temporal de O(n) a O(1)
Sin embargo, tener complejidad constante no significa automáticamente que siempre sea más rápido; el tiempo total también depende del tipo de operación
Un algoritmo O(n) puede ser más rápido que uno O(1) para cierta entrada, pero cuando el tamaño de la entrada crece, el enfoque O(1) siempre termina imponiéndose

Ordenamiento y algoritmos cuadráticos: ejemplo de Bubble Sort

Bubble Sort es un ejemplo básico de ordenamiento que organiza un arreglo repitiendo intercambios entre elementos adyacentes
Si el arreglo ya está ordenado, basta 1 pasada (O(n)); si está en orden inverso, hace falta recorrerlo n veces repetidamente → en el peor caso, el total de operaciones es n²
Un algoritmo O(n²) aumenta mucho su tiempo de ejecución en forma cuadrática a medida que crece la entrada
En el uso real, Big O siempre se basa en el peor caso (worst-case), aunque a veces también se indiquen el caso promedio o el mejor caso
Aunque la cantidad de pasadas puede reducirse según el estado inicial del arreglo, por considerar el peor caso siempre se clasifica como complejidad temporal cuadrática

Búsqueda y algoritmos logarítmicos: ejemplo de búsqueda binaria

La búsqueda binaria (Binary Search) estima el valor central de un rango ordenado y en cada paso descarta la mitad del espacio candidato
Por ejemplo, para adivinar un número específico entre 1 y 100 se necesitan como máximo 7 intentos, y entre 1 y 1,000 millones también se puede lograr en menos de 31 intentos
Como en cada paso la lista candidata se reduce a la mitad, el tiempo de ejecución es O(log n) (complejidad logarítmica)
Los algoritmos logarítmicos muestran un crecimiento extremadamente lento cuando n aumenta, por lo que son mucho más eficientes que los lineales o cuadráticos
Al comparar gráficas, la diferencia de crecimiento entre log n, n y n² se vuelve muy evidente

Aplicación práctica: consejos para mejorar la complejidad temporal

Buscar elementos en una lista

De forma básica, una función que busca un valor en un arreglo corresponde a O(n)
Si la búsqueda es frecuente, usar una estructura de datos como Set permite mejorar a O(1)
Sin embargo, el proceso de conversión con new Set(array) es en sí mismo O(n), así que solo conviene cuando habrá consultas frecuentes (hay que considerar el costo de conversión)
Ejemplo: items.has("banana") ofrece complejidad temporal constante

Escribir bucles aprovechando el índice

Es común que código como el siguiente, que usa .indexOf dentro del bucle, sea una causa de problemas de rendimiento

function buildList(items) {
  const output = [];
  for (const item of items) {
    const index = items.indexOf(item);
    output.push(`Item ${index + 1}: ${item}`);
  }
  return output.join("\n");
}

Como .indexOf es una operación O(n) dentro del bucle, en conjunto se convierte en un patrón O(n^2)

Al usar iteración basada en índice o forEach((item, index) => ...), se mejora a O(n)

function buildList(items) {
  const output = [];
  for (let i = 0; i < items.length; i++) {
    output.push(`Item ${i + 1}: ${items[i]}`);
  }
  return output.join("\n");
}

Uso de memoización

En estructuras con cálculos repetidos, como el factorial cuando se llama varias veces, se puede mejorar el rendimiento aplicando caché de resultados (usando Map)
Las consultas en Map corresponden a O(1), por lo que se minimiza el recálculo innecesario

Sin embargo, el caché ayuda a mejorar el tiempo promedio y, aunque la complejidad temporal del peor caso no cambie, sí puede aportar una mejora eficiente del rendimiento

const cache = new Map();
function factorial(n) {
  if (cache.has(n)) {
    return cache.get(n);
  }
  if (n === 0) {
    return 1;
  }
  const result = n * factorial(n - 1);
  cache.set(n, result);
  return result;
}

Evaluación del rendimiento y conclusión

Al mejorar el rendimiento del código, además de la complejidad temporal teórica, hay que confirmar con pruebas de ejecución directas si realmente hubo mejora
Big O expresa de la manera más esencial y simplificada el patrón de relación y crecimiento entre la entrada y el tiempo de ejecución
Elegir un buen algoritmo y optimizar la estructura de datos permite maximizar la eficiencia del código

Resumen

La notación Big O expresa la relación entre la entrada de una función y su tiempo de ejecución
Principales niveles de rendimiento: O(1) (constante), O(log n) (logarítmico), O(n) (lineal), O(n^2) (cuadrático)
Para escribir código eficiente, es importante elegir el algoritmo adecuado y optimizar los bucles
El rendimiento real debe medirse directamente para verificar si hubo mejora
Usar gráficas comparativas de crecimiento ayuda a entender de un vistazo las características de la complejidad temporal

1 comentarios

GN⁺ 2025-08-26

Comentarios de Hacker News

Este artículo y los comentarios en HN continúan la tradición de explicar Big O Notation y debatir sobre su uso práctico y sus detalles técnicos. Como ejemplos útiles están este artículo explicativo y este texto sobre la actitud de los expertos
- En los comentarios del artículo anterior, un usuario llamado Pyon mostró una actitud mordaz e inflexible. Pero la respuesta de Ned tampoco fue tan buena. No explica con precisión los detalles técnicos, sino que da vueltas repitiendo simplemente “ciertos detalles”. Queda la sensación de que no explicó por qué su crítica era solo una objeción puntillosa, ni por qué rechazaba también el contenido en sí. Ned sí muestra una buena dirección en cuanto a comunicación y empatía en línea. Aun así, como educador, me habría gustado que al menos una vez señalara por qué ese punto técnico era demasiado minucioso o puntilloso. El propio Ned solo dice que “no lo supo durante décadas”, y eso se siente insuficiente. Y al volver a ver el hilo original, Ned en realidad debatió de forma bastante diplomática y seria. Por eso me pregunto por qué ese análisis quedó fuera del post del blog. Personalmente no tengo claro cuáles eran esos detalles técnicos, pero me habría gustado una explicación breve al menos una vez
- Yo me acerco más al perfil de experto crítico. Cuando veo intentos de enseñar temas complejos en blogs, casi siempre termino decepcionado, porque por lo general los explican personas no expertas y se pierde precisión. El resultado es que 1) el contenido inexacto se copia y pega por todo internet, y 2) los lectores se quedan en un nivel de blog y dejan de aprender más, reforzando su ignorancia. Además, tampoco me gustó el diseño de la página. Por mi experiencia con ADHD y mala memoria, necesito que el contenido esté dividido con un formato adecuado (subtítulos/negritas/colores separadores/viñetas, etc.) para poder seguirlo, y este texto se sintió como una pared de texto. Cuanto más tiempo me toma identificar las ideas principales, más pierdo la concentración. La explicación de Big O en Simple Wikipedia es mucho más directa. En cambio, la página normal de Wikipedia de pronto mete matemáticas, y al verla uno se da cuenta de que Big O es un tema bastante más complejo de lo que parece, así que terminé pensando que “simplificarlo quizá tampoco sea tan buena idea”
- El segundo enlace no trata sobre Big-O, y no hace falta imitar ese tipo de actitud
- Ned me envió un correo hace unos días, y me da gusto también estar aportando a esta discusión
- Cuando veo textos como estos, la verdadera lección no es “si una explicación es incorrecta o puede prestarse a confusión, deja de corregirla”, sino que en internet algunos “expertos” simplemente quieren ganar la discusión. Por la actitud de Pyon, se veía bastante agresivo, casi como un troll. Jamás deberíamos sacar de ahí la conclusión de que “entonces los detalles técnicos no importan y da igual ser inexacto”
O(1) en la práctica usa una función hash, que no es algo trivial, pero sí implica un costo constante de operación. Si los datos son muy pocos, un algoritmo pésimo como O(n^2) incluso puede ser más rápido en tiempo real
- Es cierto, pero tampoco conviene exagerarlo demasiado. En la práctica ya cuesta bastante hacer entender que si algo es n^2 la computadora se va a arrastrar. Además, en algunos casos hasta se puede usar una función hash perfecta, como mod
Siento que la importancia moderna de Big-O ya no es la misma que antes. El hardware actual tiene multihilo, pipelines, NUMA, cachés complejos y demás, así que hay operaciones que terminan en menos de un ciclo y otras que tardan cientos o miles. Si uno intenta explicar un algoritmo solo por la cantidad de veces que se ejecuta el innermost loop, termina distorsionando la realidad. Y cuando se habla de Big-O, también habría que mencionar siempre otras notaciones como Big-Omega. (Por cierto, también disfruté la animación sobre Big-O)
- La teoría de Big-O nació precisamente para definir la cantidad de operaciones independientemente de ese tipo de factores dependientes del dispositivo. En ese sentido, es una herramienta que no envejece. (Un buen expositor normalmente también menciona que “constantes como C pueden ser muy importantes cuando N es pequeño”)
Lo realmente interesante es que en computación cuántica hay operaciones cuyo costo crece como O(n^7) con respecto al número de átomos, pero aun así los científicos no tienen miedo de ejecutar esos cálculos. Porque N es lo bastante pequeño, las computadoras y la memoria siguen mejorando, y el resultado tiene un valor enorme. (No soy especialista en ciencias de la computación, así que disculpen si usé mal la notación O())
- Puedes decir simplemente que “crece proporcionalmente a n^7”. Si dices O(n^7), la mayoría te va a entender, pero matemáticamente O solo representa una cota superior, así que no es estrictamente exacto. Si quisieras ser realmente preciso, correspondería escribir algo como Ω(n^7)
Me encantó la visualización. Incluso habiendo estudiado algoritmos antes, seguir viéndolo de forma visual me ayuda muchísimo
Tal vez porque estudié ingeniería eléctrica, siempre sentí que Big O Notation se trataba como un concepto que se salta por encima a grandes rasgos. Siempre lo manejaban como si fuera algo obvio, así que no recuerdo haber visto una explicación realmente amable. Me da curiosidad en qué nivel de matemáticas o computación se presenta por primera vez este concepto
- En un curso de Discrete Math de la carrera fue donde aprendí Big-O de la forma más sistemática
- En mi universidad lo enseñaban en Algorithm Analysis (materia obligatoria), junto con Big-O y varios métodos de demostración. Pero esa materia se llevaba casi siempre en 3.º o 4.º año, y en la práctica había la suposición implícita de que uno ya había absorbido algo del concepto desde 1.º año (probablemente por haberlo aprendido alrededor de forma informal)
- Matemáticamente, que una función f(x) sea O(g(x)) significa que f(x)/g(x) satisface, para alguna constante C, que “para todo x, f(x)/g(x) < C”. En computación, f(x) muchas veces representa una complejidad como la cantidad de operaciones de cierto algoritmo
- El diseño de Big-O Notation admite varias interpretaciones. Por ejemplo, si defines un algoritmo por el número de pasos de una Turing Machine, entonces no puede existir un algoritmo de tiempo logarítmico y O(log n) pasa a tratarse como O(1)
- Lo aprendí en una materia obligatoria de primer año de computación. No tiene gran misterio: solo describe cómo crece la cantidad de operaciones cuando aumenta el volumen de datos de entrada. Parece difícil por fuera, pero en realidad es muy simple y claro
La visualización dinámica ayudó muchísimo a entenderlo. Ojalá hagan más lecciones y materiales como este
- Gracias por ese comentario, me alegra mucho
Cada vez que aparece un hilo sobre Big-O Notation, siempre espero que alguien explique cómo se conecta el concepto con el anime The Big O. Todavía no entiendo muy bien de qué va ese anime
- (se toma 4 cervezas de un trago)Bueno, escucha. Ese anime es como si mezclaras, en ese orden, Pacific Rim, Dark City y The Matrix
Personalmente, creo que la manera más efectiva de entender Big O Notation es relacionarlo con situaciones cotidianas
Me parece un material hermoso. Les mandé una señal y espero que haya llegado bien; siento como si me hubiera caído una cucharadita de dopamina sin querer
- Sí llegó bien. Gracias