AlegsaOnline.com

Notación Big O: cota superior y complejidad de algoritmos

Aprende la notación Big O: cota superior y análisis de la complejidad de algoritmos con ejemplos claros para medir eficiencia y tiempo en el peor caso.

Autor: Leandro Alegsa

13-01-2026

En matemáticas y ciencias de la computación, la notación Big O es una forma de comparar las tasas de crecimiento de diferentes funciones. A menudo se utiliza para comparar la eficiencia de diferentes algoritmos, lo que se hace calculando cuánta memoria se necesita y cuánto tiempo tarda en completarse.

La notación Big O se utiliza a menudo para identificar el grado de complejidad de un problema, también conocido como clase de complejidad del problema. El matemático Paul Bachmann (1837-1920) fue el primero en utilizar esta notación, en la segunda edición de su libro "Analytische Zahlentheorie", en 1896. Edmund Landau (1877-1938) popularizó la notación. Por esta razón, cuando se habla de los símbolos de Landau, se hace referencia a esta notación.

La notación Big O recibe su nombre del término "orden de la función", que se refiere al crecimiento de las funciones. La notación Big O se utiliza para encontrar el límite superior (la cantidad más alta posible) de la tasa de crecimiento de la función, lo que significa que calcula el tiempo más largo que tardará en convertir la entrada en la salida. Esto significa que un algoritmo puede agruparse según el tiempo que puede tardar en el peor de los casos, en el que se tomará siempre el camino más largo.

Más concretamente, dadas dos funciones positivas f ( x ) {\displaystyle f(x)} f(x) y g ( x ) {\displaystyle g(x)} $g(x)$ , decimos que f {\displaystyle f} está en el gran O de g {\displaystyle g} (escrito f ∈ O ( g ) {\displaystyle f\in O(g)} $f\in O(g)$ ) si para un tamaño suficientemente grande x {\displaystyle x} , f $f(x)\leq k\cdot g(x)$ para alguna constante k {\displaystyle k} .

Big O es una expresión que encuentra el tiempo de ejecución en el peor de los casos, mostrando la eficiencia de un algoritmo sin tener que ejecutar el programa en un ordenador. También es útil debido al hecho de que diferentes ordenadores pueden tener un hardware diferente, y por lo tanto necesitan diferentes cantidades de tiempo para completarlo. Dado que Big O siempre asume el peor caso, puede mostrar una medida consistente de la velocidad: independientemente del hardware, O ( 1 ) {\displaystyle O(1)} $O(1)$ siempre se va a completar más rápido que O ( n ! ) {\displaystyle O(n!)} $O(n!)$ , porque tienen diferentes niveles de eficiencia.

Definición y matices prácticos

En términos prácticos, decir "f(n) ∈ O(g(n))" significa que existe una constante positiva k y un n0 tal que para todo n ≥ n0 se cumple f(n) ≤ k·g(n). Big O describe un límite superior asintótico: ignora constantes multiplicativas y términos de menor orden porque, al crecer n, esos términos dejan de ser relevantes frente al término dominante.

Es importante distinguir Big O de otras notaciones asintóticas:

Big Omega (Ω): límite inferior asintótico. f(n) ∈ Ω(g(n)) si, para n suficientemente grande, f(n) ≥ c·g(n) para alguna constante c > 0.
Big Theta (Θ): acotación ajustada. f(n) ∈ Θ(g(n)) si f(n) ∈ O(g(n)) y f(n) ∈ Ω(g(n)); es decir, g(n) es una cota superior y también una cota inferior hasta constantes.

Casos: peor, promedio y mejor

Big O suele usarse para expresar la complejidad en el peor de los casos, pero la notación en sí no requiere que sea el peor caso —simplemente indica una cota superior. Para análisis más precisos conviene distinguir:

Peor caso (worst-case): tiempo máximo que puede tomar el algoritmo sobre entradas de tamaño n. Es la interpretación más común de Big O en documentación técnica.
Caso promedio (average-case): tiempo esperado sobre una distribución de entradas; requiere modelar probabilísticamente las entradas.
Mejor caso (best-case): tiempo mínimo posible; se expresa a menudo con Big Omega.

Ejemplos comunes de complejidad temporal

O(1) — Constante: operaciones que no dependen del tamaño de la entrada (acceso a una posición de un arreglo, asignación simple).
O(log n) — Logarítmica: búsquedas en estructuras ordenadas como binary search en un arreglo ordenado; cada paso reduce el problema exponencialmente.
O(n) — Lineal: recorrer una lista una vez (ej.: búsqueda lineal).
O(n log n): algoritmos de ordenación eficientes como merge sort o heapsort en promedio y en el peor caso.
O(n²) — Cuadrática: algoritmos con bucles anidados sobre la entrada, como el bubble sort y muchos algoritmos ingenuos de comparación par a par.
O(2ⁿ) — Exponencial: algoritmos que generan todas las combinaciones de subconjuntos (ej.: solución ingenua de problemas NP-completos), crece muy rápido.
O(n!) — Factorial: típicamente aparece en problemas que requieren probar todas las permutaciones (ej.: el viajante de comercio con fuerza bruta).

Ejemplos prácticos

Búsqueda lineal en un arreglo sin ordenar: O(n) en el peor caso.
Búsqueda binaria en un arreglo ordenado: O(log n) en el peor caso.
Merge sort (ordenación por mezcla): O(n log n) en el peor caso; usa memoria adicional para la mezcla.
Bubble sort: O(n²) en tiempo; O(1) en espacio extra si se implementa in-place.

Complejidad espacial

Además del tiempo de ejecución, Big O puede describir la complejidad espacial: la cantidad de memoria adicional usada por un algoritmo en función del tamaño de la entrada. Por ejemplo, un algoritmo in-place puede tener complejidad espacial O(1), mientras que uno que necesita copiar la entrada puede requerir O(n).

Cómo determinar la Big O de un algoritmo

Pasos prácticos:

Identificar las operaciones dominantes que crecen con n (bucles, recursiones).
Contar el número de veces que se ejecutan esas operaciones en función de n.
Sumar los costos y simplificar: eliminar constantes multiplicativas y términos de menor orden quedándote con el término de mayor crecimiento.

En algoritmos recursivos, es útil establecer una ecuación de recurrencia y resolverla (por ejemplo, usando el teorema maestro para divisiones recursivas típicas).

Consejos y consideraciones

Big O describe comportamiento asintótico: para n pequeños, constantes y detalles de implementación pueden hacer que un algoritmo con peor Big O sea más rápido en la práctica.
Optimizar la complejidad asintótica suele ser más relevante que microoptimizar constantes cuando se trabaja con grandes volúmenes de datos.
Elegir la estructura de datos adecuada (árboles balanceados, tablas hash, heaps) puede cambiar drásticamente la complejidad de operaciones comunes.
No confundir coste teórico con coste real: la elección de hardware, cachés y paralelismo también afecta el rendimiento.

En resumen, la notación Big O es una herramienta esencial para describir y comparar el comportamiento asintótico de algoritmos y funciones, ofreciendo una forma estandarizada de hablar sobre eficiencia y escalabilidad sin depender de implementaciones concretas o hardware.

Ejemplos

Todos los ejemplos siguientes utilizan código escrito en Python. Tenga en cuenta que esta no es una lista completa de tipos de Big O.

Constantemente

O ( 1 ) {\displaystyle O(1)} $O(1)$ siempre tarda la misma cantidad de tiempo independientemente de la entrada. Por ejemplo, tomemos una función que acepta un número entero (llamado x) y devuelve el doble de su valor:

def double(x): return x * 2 #Devuelve el valor de x por 2

Después de aceptar la entrada, esta función siempre tardará un paso en devolver una salida. Es constante porque siempre tomará la misma cantidad de tiempo, por lo que es O ( 1 ) {\displaystyle O(1)} $O(1)$ .

Lineal

O ( n ) {\displaystyle O(n)} $O(n)$ aumenta según el tamaño de la entrada, representado por n {\displaystyle n} . Por ejemplo, para la siguiente función que acepta n y devuelve todos los números de 1 a n:

def count(n): i = 1 #Crea un contador llamado "i" con un valor de 1 mientras i <= n: #Mientras i es menor o igual que n print(i) #Imprime el valor de i i = i + 1 #Redefine i como "el valor de i + 1"

Si introdujéramos el valor de 5, entonces esto daría como resultado 1 , 2 , 3 , 4 , 5 {\diseño 1,2,3,4,5} $1,2,3,4,5$ , requiriendo 5 bucles para completarse. Del mismo modo, si introducimos 100, entonces saldría 1 , 2 $1,2,3...98,99,100$ , requiriendo 100 bucles para completarse. Si la entrada es n {\displaystyle n} , entonces el tiempo de ejecución del algoritmo es exactamente n {\displaystyle n} bucles cada vez, por lo tanto es O ( n ) {\displaystyle O(n)} $O(n)$ .

Factorial

O ( n ! ) {\Nsegún el estilo O(n!)} $O(n!)$ aumenta en cantidades factoriales, lo que significa que el tiempo que se tarda aumenta masivamente con la entrada. Por ejemplo, supongamos que deseamos visitar cinco ciudades del mundo y queremos ver todas las ordenaciones posibles (permutaciones). Un algoritmo que podríamos escribir utilizando la biblioteca itertools de Python es el siguiente:

import itertools #Importar la biblioteca itertools ciudades = ['Londres', 'París', 'Berlín', 'Ámsterdam', 'Roma'] #Una matriz de nuestras ciudades elegidas def permutations(cities): #Tomando una matriz de ciudades como entrada: for i in itertools.permutations(cities): #Por cada permutación de nuestros elementos (asignados a la variable "i") print(i) #Salida i

Este algoritmo calculará cada permutación única de nuestras ciudades y luego dará una salida. Los ejemplos de salida incluirán:

('Londres', 'París', 'Berlín', 'Ámsterdam', 'Roma') ('Londres', 'París', 'Berlín', 'Roma', 'Ámsterdam') ('Londres', 'París', 'Ámsterdam', 'Berlín', 'Roma') ... ('Roma', 'Ámsterdam', 'París', 'Berlín', 'Londres') ('Roma', 'Ámsterdam', 'Berlín', 'Londres', 'París') ('Roma', 'Ámsterdam', 'Berlín', 'París')

Aquí, nuestra lista de entrada tiene 5 elementos, y por cada selección nuestras opciones restantes disminuyen en 1. En otras palabras, nuestras 5 entradas eligen $5\times 4\times 3\times 2\times 1$ elementos (o 5 ! {\displaystyle 5!} $5!$ ). ¡Si nuestra entrada tiene n {\displaystyle n} ciudades, entonces el número de salidas es n ! {\displaystyle n!} $n!$ ; en general, suponiendo que pasamos por cada permutación, entonces necesitaremos O ( n ! ) {\displaystyle O(n!)} bucles $O(n!)$ para completarla.

Notación Little-o

Un concepto relacionado con la notación big-O es la notación little-o. Big-O se utiliza para decir que una función no crece más rápido que otra función, mientras que little-o se utiliza para decir que una función crece más lentamente que otra función. Si dos funciones crecen al mismo ritmo, se puede utilizar big-O pero no little-o. La diferencia entre big-O y little-o es similar a la diferencia entre ≤ {\displaystyle \leq } $\leq$ y < {\displaystyle <} $<$ .

Si f ( x ) {\displaystyle f(x)} crece más lentamente que g ( x ) {\displaystyle g(x)} $g(x)$ , entonces f ( x ) ∈ O ( $f(x)\in O(g(x))$ y f ( x ) ∈ o $f(x)\in o(g(x))$ .
Si f ( x ) {\displaystyle f(x)} crece al mismo ritmo que g ( x ) {\displaystyle g(x)} $g(x)$ , entonces f ( x ) ∈ O ( $f(x)\in O(g(x))$ pero f ( x ) ∉ o $f(x)\not \in o(g(x))$ .
Si f ( x ) {\displaystyle f(x)} crece a mayor velocidad que g ( x ) {\displaystyle g(x)} $g(x)$ , entonces f ( x ) ∉ O ( $f(x)\not \in O(g(x))$ y f ( x ) ∉ o $f(x)\not \in o(g(x))$ .

Preguntas y respuestas

P: ¿Qué es la notación Big O?

R: La notación Big O es una forma de comparar las tasas de crecimiento de diferentes funciones, a menudo utilizada para comparar la eficiencia de diferentes algoritmos mediante el cálculo de la cantidad de memoria y tiempo que se necesita para completarlos. También puede utilizarse para identificar la complejidad de un problema.

P: ¿Quién fue el primero en utilizar esta notación?

R: El matemático Paul Bachmann (1837-1920) fue el primero en utilizar esta notación en su libro "Analytische Zahlentheorie" en 1896.

P: ¿Qué significa la O grande?

R: Big O significa "orden de la función", que se refiere a la tasa de crecimiento de las funciones.

P: ¿Cómo se utiliza la Big O?

R: La notación Big O se utiliza para encontrar un límite superior (la cantidad más alta posible) en la tasa de crecimiento de la función, lo que significa que calcula el tiempo más largo que tardará en convertir una entrada en una salida. Esto significa que los algoritmos pueden agruparse por el tiempo que tardan en el peor de los casos, en el que se tomará siempre el camino más largo.

P: ¿Qué son los símbolos de Landau?

R: Los símbolos de Landau se refieren a la notación Big O, llamada así por Edmund Landau (1877-1938), que popularizó esta notación.

P: ¿Por qué es útil la Big O?

R: La Big O nos permite medir la velocidad sin tener que ejecutar los programas en los ordenadores, ya que siempre asume el peor de los casos, lo que la hace consistente independientemente de las diferencias de hardware entre los ordenadores. También muestra la eficiencia de un algoritmo sin tener que ejecutarlo realmente en un ordenador.