Notación O grande

Aproximación de ajuste
Conceptos
Órdenes de aproximación Análisis de escala Notación O grande Ajuste de curvas Falsa precisión Cifras significativas
Otros fundamentos
Aproximación Error de generalización Polinomio de Taylor Modelado científico
en a mi

La notación Big O es una notación matemática que describe el comportamiento límite de una función cuando el argumento tiende hacia un valor particular o hacia el infinito. Big O es miembro de una familia de notaciones inventadas por los matemáticos alemanes Paul Bachmann , ^[1] Edmund Landau , ^[2] y otros, llamadas colectivamente notación Bachmann-Landau o notación asintótica . La letra O fue elegida por Bachmann para representar Ordnung , es decir, el orden de aproximación .

En informática , la notación O mayúscula se utiliza para clasificar algoritmos según cómo crecen sus requisitos de tiempo de ejecución o espacio a medida que crece el tamaño de entrada. ^[3] En teoría analítica de números , la notación O mayúscula se utiliza a menudo para expresar un límite en la diferencia entre una función aritmética y una aproximación mejor entendida; un ejemplo famoso de tal diferencia es el término restante en el teorema de los números primos . La notación O mayúscula también se utiliza en muchos otros campos para proporcionar estimaciones similares.

La notación O mayúscula caracteriza las funciones según sus tasas de crecimiento: distintas funciones con la misma tasa de crecimiento asintótico pueden representarse utilizando la misma notación O. Se utiliza la letra O porque la tasa de crecimiento de una función también se conoce como el orden de la función . Una descripción de una función en términos de notación O mayúscula generalmente solo proporciona un límite superior para la tasa de crecimiento de la función.

Asociadas con la notación O grande hay varias notaciones relacionadas, que utilizan los símbolos o , Ω, ω y Θ , para describir otros tipos de límites en las tasas de crecimiento asintótico.

Sea la función a estimar una función de valor real o complejo , y sea la función de comparación una función de valor real. Dejemos que ambas funciones se definan en algún subconjunto ilimitado de los números reales positivos , y sean distintas de cero (a menudo, pero no necesariamente, estrictamente positivas) para todos los valores suficientemente grandes de ^[4] Se escribe y se lee " es grande O de " o más a menudo " es del orden de " si el valor absoluto de es como máximo un múltiplo constante positivo del valor absoluto de para todos los valores suficientemente grandes de Es decir, si existe un número real positivo y un número real tal que En muchos contextos, la suposición de que estamos interesados ​​en la tasa de crecimiento a medida que la variable tiende a infinito o a cero se deja sin establecer, y se escribe de forma más sencilla que La notación también se puede utilizar para describir el comportamiento de cerca de algún número real (a menudo, ): decimos si existen números positivos y tales que para todos definidos con Como es distinto de cero para valores adecuadamente grandes (o pequeños) de ambas definiciones se pueden unificar utilizando el límite superior : si Y en ambas definiciones el punto límite (sea o no) un punto de clúster de los dominios de e i. es decir, en cada entorno de deben existir infinitos puntos en común. Además, como se señala en el artículo sobre el límite inferior y el límite superior , el (al menos en la línea de números reales extendida ) siempre existe.${\estilo de visualización f,}$${\estilo de visualización \ g\ ,}$ ${\estilo de visualización g(x)}$${\estilo de visualización x.}$$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ como }}x\to \infty }$$${\estilo de visualización \ f(x)\ }$${\estilo de visualización g(x)}$${\estilo de visualización f(x)}$${\estilo de visualización g(x)}$${\estilo de visualización f(x)}$${\estilo de visualización g(x)}$${\estilo de visualización x.}$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}}$${\estilo de visualización M}$$estilo de visualización x_{0}}$$${\displaystyle |f(x)|\leq M\ |g(x)|\quad {\text{ para todo }}x\geq x_{0}~.}$$${\estilo de visualización \ x\}$$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}.}$$${\estilo de visualización f}$${\estilo de visualización a}$${\displaystyle a=0}$$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ como }}\ x\to a}$$${\estilo de visualización \delta}$${\estilo de visualización M}$${\estilo de visualización x}$${\displaystyle 0<|xa|<\delta,}$$${\displaystyle |f(x)|\leq M|g(x)|.}$$${\estilo de visualización g(x)}$${\estilo de visualización x,}$$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ como }}\ x\to a}$$$${\displaystyle \limsup _{x\to a}{\frac {\left|f(x)\right|}{\left|g(x)\right|}}<\infty .}$$ ${\displaystyle a}$${\displaystyle \infty }$${\displaystyle f}$${\displaystyle g,}$${\displaystyle a}$${\displaystyle \textstyle \limsup _{x\to a}}$

En informática, es común una definición ligeramente más restrictiva: y se requiere que ambos sean funciones desde algún subconjunto ilimitado de los números enteros positivos hasta los números reales no negativos; entonces, si existen números enteros positivos y tales que para todos ^[5]${\displaystyle f}$${\displaystyle g}$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}}$${\displaystyle M}$${\displaystyle n_{0}}$${\displaystyle |f(n)|\leq M|g(n)|}$${\displaystyle n\geq n_{0}.}$

En el uso típico, la notación O es asintótica, es decir, se refiere a valores x muy grandes . En este contexto, la contribución de los términos que crecen "más rápidamente" hará que los demás sean irrelevantes. Como resultado, se pueden aplicar las siguientes reglas de simplificación:

• Si f ( x ) es una suma de varios términos, si hay uno con la mayor tasa de crecimiento, se puede conservar y omitir todos los demás.
• Si f ( x ) es un producto de varios factores, se pueden omitir todas las constantes (factores del producto que no dependen de x ).

Por ejemplo, sea f ( x ) = 6 x ⁴ − 2 x ³ + 5 , y supongamos que deseamos simplificar esta función, utilizando la notación O , para describir su tasa de crecimiento a medida que x tiende al infinito. Esta función es la suma de tres términos: 6 x ⁴ , −2 x ³ y 5 . De estos tres términos, el que tiene la tasa de crecimiento más alta es el que tiene el mayor exponente en función de x , es decir, 6 x ⁴ . Ahora se puede aplicar la segunda regla: 6 x ⁴ es un producto de 6 y x ⁴ en el que el primer factor no depende de x . Omitir este factor da como resultado la forma simplificada x ⁴ . Por lo tanto, decimos que f ( x ) es una "O grande" de x ⁴ . Matemáticamente, podemos escribir f ( x ) = O ( x ⁴ ) . Se puede confirmar este cálculo usando la definición formal: sea f ( x ) = 6 x ⁴ − 2 x ³ + 5 y g ( x ) = x ⁴ . Aplicando la definición formal de arriba, la afirmación de que f ( x ) = O ( x ⁴ ) es equivalente a su desarrollo, para alguna elección adecuada de un número real x ₀ y un número real positivo M y para todo x > x ₀ . Para probar esto, sea x ₀ = 1 y M = 13 . Entonces, para todo x > x ₀ : entonces$${\displaystyle |f(x)|\leq Mx^{4}}$$$${\displaystyle {\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}}$$$${\displaystyle |6x^{4}-2x^{3}+5|\leq 13x^{4}.}$$

La notación Big O tiene dos áreas principales de aplicación:

• En matemáticas , se utiliza comúnmente para describir qué tan cerca una serie finita se aproxima a una función dada, especialmente en el caso de una serie de Taylor truncada o una expansión asintótica.
• En informática , es útil en el análisis de algoritmos.

En ambas aplicaciones, la función g ( x ) que aparece dentro de O (·) se elige típicamente para que sea lo más simple posible, omitiendo factores constantes y términos de orden inferior.

Hay dos usos formalmente cercanos, pero notablemente diferentes, de esta notación: ^{[ cita requerida ]}

• asintóticas infinitas
• asintótica infinitesimal

Sin embargo, esta distinción sólo es aplicable y no de principio: la definición formal de la "gran O" es la misma para ambos casos, sólo que con límites diferentes para el argumento de la función. ^{[ ¿ Investigación original? ]}

La notación O grande es útil cuando se analizan algoritmos para determinar su eficiencia. Por ejemplo, el tiempo (o la cantidad de pasos) que se necesitan para completar un problema de tamaño n puede ser T ( n ) = 4 n ² − 2 n + 2 . A medida que n se hace grande, el término n ² pasará a dominar, de modo que todos los demás términos pueden ignorarse; por ejemplo, cuando n = 500 , el término 4 n ² es 1000 veces más grande que el término 2 n . Ignorar este último tendría un efecto insignificante en el valor de la expresión para la mayoría de los propósitos. Además, los coeficientes se vuelven irrelevantes si los comparamos con cualquier otro orden de expresión, como una expresión que contenga un término n ³ o n ⁴ . Incluso si T ( n ) = 1.000.000 n ² , si U ( n ) = n ³ , este último siempre superará al primero una vez que n crezca más de 1.000.000 , es decir, T (1.000.000) = 1.000.000 ³ = U (1.000.000) . Además, el número de pasos depende de los detalles del modelo de máquina en el que se ejecuta el algoritmo, pero los diferentes tipos de máquinas suelen variar solo por un factor constante en el número de pasos necesarios para ejecutar un algoritmo. Por lo tanto, la notación O mayúscula captura lo que queda: escribimos

${\displaystyle T(n)=O(n^{2})}$

o

${\displaystyle T(n)\in O(n^{2})}$

y decir que el algoritmo tiene una complejidad temporal de orden n ^2. El signo " = " no pretende expresar "es igual a" en su sentido matemático normal, sino más bien un "es" más coloquial, por lo que la segunda expresión a veces se considera más precisa (ver la discusión sobre el "signo igual" a continuación) mientras que la primera es considerada por algunos como un abuso de notación . ^[6]

La O mayúscula también se puede utilizar para describir el término de error en una aproximación a una función matemática. Los términos más significativos se escriben explícitamente y luego los términos menos significativos se resumen en un único término O mayúscula. Consideremos, por ejemplo, la serie exponencial y dos expresiones de la misma que son válidas cuando x es pequeño:

${\displaystyle {\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all finite }}x\\[4pt]&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\[4pt]&=1+x+O(x^{2})&{\text{as }}x\to 0\end{aligned}}}$

La expresión del medio (la que tiene O ( x ³ )) significa que el valor absoluto del error e ^x − (1 + x + x ² /2) es como máximo algunas veces constantes | x ³ | cuando x está lo suficientemente cerca de 0.

Si la función f puede escribirse como una suma finita de otras funciones, entonces la que crece más rápidamente determina el orden de f ( n ) . Por ejemplo,

${\displaystyle f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .}$

En particular, si una función puede estar acotada por un polinomio en n , entonces, como n tiende a infinito , se pueden ignorar los términos de orden inferior del polinomio. Los conjuntos O ( n ^c ) y O ( c ⁿ ) son muy diferentes. Si c es mayor que uno, entonces este último crece mucho más rápido. Una función que crece más rápido que n ^c para cualquier c se llama superpolinomio . Una que crece más lentamente que cualquier función exponencial de la forma c ⁿ se llama subexponencial . Un algoritmo puede requerir tiempo que sea tanto superpolinomio como subexponencial; ejemplos de esto incluyen los algoritmos más rápidos conocidos para la factorización de números enteros y la función n ^{log n} .

Podemos ignorar cualquier potencia de n dentro de los logaritmos. El conjunto O (log n ) es exactamente el mismo que O (log( n ^c )) . Los logaritmos difieren solo por un factor constante (ya que log( n ^c ) = c log n ) y, por lo tanto, la notación O grande ignora eso. De manera similar, los logaritmos con diferentes bases constantes son equivalentes. Por otro lado, los exponenciales con diferentes bases no son del mismo orden. Por ejemplo, 2 ⁿ y 3 ⁿ no son del mismo orden.

Cambiar las unidades puede afectar o no el orden del algoritmo resultante. Cambiar las unidades es equivalente a multiplicar la variable apropiada por una constante donde sea que aparezca. Por ejemplo, si un algoritmo se ejecuta en el orden de n ² , reemplazar n por cn significa que el algoritmo se ejecuta en el orden de c ² n ² , y la notación O grande ignora la constante c ² . Esto se puede escribir como c ² n ² = O( n ² ) . Sin embargo, si un algoritmo se ejecuta en el orden de 2 ⁿ , reemplazar n por cn da 2 ^cn = (2 ^c ) ⁿ . Esto no es equivalente a 2 ⁿ en general. Cambiar las variables también puede afectar el orden del algoritmo resultante. Por ejemplo, si el tiempo de ejecución de un algoritmo es O ( n ) cuando se mide en términos de la cantidad n de dígitos de un número de entrada x , entonces su tiempo de ejecución es O (log x ) cuando se mide como una función del número de entrada x en sí, porque n = O (log x ) .

${\displaystyle f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})}$

${\displaystyle f\cdot O(g)=O(fg)}$

Si y entonces . Se sigue que si y entonces . En otras palabras, esta segunda afirmación dice que es un cono convexo .${\displaystyle f_{1}=O(g_{1})}$${\displaystyle f_{2}=O(g_{2})}$${\displaystyle f_{1}+f_{2}=O(\max(g_{1},g_{2}))}$${\displaystyle f_{1}=O(g)}$${\displaystyle f_{2}=O(g)}$${\displaystyle f_{1}+f_{2}\in O(g)}$${\displaystyle O(g)}$

Sea k una constante distinta de cero. Entonces . En otras palabras, si , entonces ${\displaystyle O(|k|\cdot g)=O(g)}$${\displaystyle f=O(g)}$${\displaystyle k\cdot f=O(g).}$

La O mayúscula (y la o minúscula, Ω, etc.) también se puede utilizar con múltiples variables. Para definir la O mayúscula formalmente para múltiples variables, supongamos que y son dos funciones definidas en algún subconjunto de . Decimos${\displaystyle f}$${\displaystyle g}$${\displaystyle \mathbb {R} ^{n}}$

${\displaystyle f(\mathbf {x} ){\text{ is }}O(g(\mathbf {x} ))\quad {\text{ as }}\mathbf {x} \to \infty }$

si y sólo si existen constantes y tales que para todos con para algunos ^[7] De manera equivalente, la condición de que para algunos puede escribirse , donde denota la norma de Chebyshev . Por ejemplo, la afirmación${\displaystyle M}$${\displaystyle C>0}$${\displaystyle |f(\mathbf {x} )|\leq C|g(\mathbf {x} )|}$${\displaystyle \mathbf {x} }$${\displaystyle x_{i}\geq M}$${\displaystyle i.}$${\displaystyle x_{i}\geq M}$${\displaystyle i}$${\displaystyle \|\mathbf {x} \|_{\infty }\geq M}$${\displaystyle \|\mathbf {x} \|_{\infty }}$

${\displaystyle f(n,m)=n^{2}+m^{3}+O(n+m)\quad {\text{ as }}n,m\to \infty }$

afirma que existen constantes C y M tales que

${\displaystyle |f(n,m)-(n^{2}+m^{3})|\leq C|n+m|}$

siempre que se cumpla o . Esta definición permite que todas las coordenadas de aumenten hasta el infinito. En particular, la afirmación${\displaystyle m\geq M}$${\displaystyle n\geq M}$${\displaystyle \mathbf {x} }$

${\displaystyle f(n,m)=O(n^{m})\quad {\text{ as }}n,m\to \infty }$

(es decir, ) es bastante diferente de${\displaystyle \exists C\,\exists M\,\forall n\,\forall m\,\cdots }$

${\displaystyle \forall m\colon ~f(n,m)=O(n^{m})\quad {\text{ as }}n\to \infty }$

(es decir, ).${\displaystyle \forall m\,\exists C\,\exists M\,\forall n\,\cdots }$

Según esta definición, el subconjunto en el que se define una función es significativo al generalizar enunciados del contexto univariante al contexto multivariante. Por ejemplo, si y , entonces si restringimos y a , pero no si están definidos en .${\displaystyle f(n,m)=1}$${\displaystyle g(n,m)=n}$${\displaystyle f(n,m)=O(g(n,m))}$${\displaystyle f}$${\displaystyle g}$${\displaystyle [1,\infty )^{2}}$${\displaystyle [0,\infty )^{2}}$

Esta no es la única generalización de O grande a funciones multivariadas y, en la práctica, existe cierta inconsistencia en la elección de la definición. ^[8]

La afirmación " f ( x )   es O [ g ( x ) ]   ", tal como se definió anteriormente, se escribe generalmente como f ( x ) = O [ g ( x ) ]   . Algunos consideran que esto es un abuso de notación , ya que el uso del signo igual podría ser engañoso, ya que sugiere una simetría que esta afirmación no tiene. Como dice de Bruijn , O [ x ] = O [ x ² ]   es verdadera, pero O [ x ² ] = O [ x ]   no lo es. ^[9] Knuth describe tales afirmaciones como "igualdades unidireccionales", ya que si los lados pudieran invertirse, "podríamos deducir cosas ridículas como n = n ² a partir de las identidades n = O [ n ² ]   y n ² = O [ n ² ]   ". ^[10] En otra carta, Knuth también señaló que                

"el signo de igualdad no es simétrico con respecto a tales notaciones", [como, en esta notación,] "los matemáticos habitualmente usan el signo '=' como usan la palabra 'es' en inglés: Aristóteles es un hombre, pero un hombre no es necesariamente Aristóteles". ^[11]

Por estas razones, sería más preciso utilizar la notación de conjuntos y escribir f ( x ) ∈ O [ g ( x ) ]   (que se lee como: " f ( x )   es un elemento de O [ g ( x ) ]   ", o " f ( x )   está en el conjunto O [ g ( x ) ] "), pensando en O [ g ( x ) ]   como la clase de todas las funciones h ( x )   tales que | h ( x ) | ≤ C | g ( x ) |   para algún número real positivo C . ^[10] Sin embargo, el uso del signo igual es habitual. ^{[9] [10]}               

La notación O grande también se puede utilizar junto con otros operadores aritméticos en ecuaciones más complicadas. Por ejemplo, h ( x ) + O ( f ( x )) denota la colección de funciones que tienen el crecimiento de h ( x ) más una parte cuyo crecimiento está limitado al de f ( x ). Por lo tanto,

${\displaystyle g(x)=h(x)+O(f(x))}$

expresa lo mismo que

${\displaystyle g(x)-h(x)=O(f(x)).}$

Supongamos que se está desarrollando un algoritmo para operar sobre un conjunto de n elementos. Sus desarrolladores están interesados ​​en encontrar una función T ( n ) que exprese cuánto tiempo tardará en ejecutarse el algoritmo (en alguna medida arbitraria de tiempo) en términos del número de elementos en el conjunto de entrada. El algoritmo funciona llamando primero a una subrutina para ordenar los elementos del conjunto y luego realizar sus propias operaciones. La ordenación tiene una complejidad temporal conocida de O ( n ^{2 ), y después de que se ejecuta la subrutina, el algoritmo debe realizar} 55 n ³ + 2 n + 10 pasos adicionales antes de terminar. Por lo tanto, la complejidad temporal total del algoritmo se puede expresar como T ( n ) = 55 n ³ + O ( n ² ) . Aquí los términos 2 n + 10 se subsumen dentro del O ( n ² ) de crecimiento más rápido. Nuevamente, este uso ignora parte del significado formal del símbolo "=", pero permite utilizar la notación O grande como una especie de marcador de posición conveniente.

En un uso más complicado, O (·) puede aparecer en diferentes lugares en una ecuación, incluso varias veces en cada lado. Por ejemplo, lo siguiente es cierto para : El significado de tales afirmaciones es el siguiente: para cualquier función que satisfaga cada O (·) en el lado izquierdo, hay algunas funciones que satisfacen cada O (·) en el lado derecho, de modo que al sustituir todas estas funciones en la ecuación los dos lados son iguales. Por ejemplo, la tercera ecuación anterior significa: "Para cualquier función f ( n ) = O (1), hay alguna función g ( n ) = O ( e ⁿ ) tal que n ^{f ( n )} = g ( n )". En términos de la "notación de conjuntos" anterior, el significado es que la clase de funciones representadas por el lado izquierdo es un subconjunto de la clase de funciones representadas por el lado derecho. En este uso, el "=" es un símbolo formal que, a diferencia del uso habitual de "=", no es una relación simétrica . Así, por ejemplo, n ^{O (1)} = O ( e ⁿ ) no implica la afirmación falsa O ( e ⁿ ) = n ^{O (1)} .${\displaystyle n\to \infty }$$${\displaystyle {\begin{aligned}(n+1)^{2}&=n^{2}+O(n),\\(n+O(n^{1/2}))\cdot (n+O(\log n))^{2}&=n^{3}+O(n^{5/2}),\\n^{O(1)}&=O(e^{n}).\end{aligned}}}$$

La O grande se escribe como una "O" mayúscula en cursiva, como en el siguiente ejemplo: . ^{[12] [13]} En TeX , se produce simplemente escribiendo O dentro del modo matemático. A diferencia de las notaciones de Bachmann–Landau con nombre griego, no necesita un símbolo especial. Sin embargo, algunos autores usan la variante caligráfica en su lugar. ^{[14] [15]}${\displaystyle O(n^{2})}$${\displaystyle {\mathcal {O}}}$

A continuación se incluye una lista de clases de funciones que se encuentran comúnmente al analizar el tiempo de ejecución de un algoritmo. En cada caso, c es una constante positiva y n aumenta sin límite. Las funciones de crecimiento más lento generalmente se enumeran primero.

Notación	Nombre	Ejemplo
${\displaystyle O(1)}$	constante	Encontrar el valor mediano de una matriz ordenada de números; Cálculo ; Uso de una tabla de búsqueda de tamaño constante${\displaystyle (-1)^{n}}$
${\displaystyle O(\alpha (n))}$	función de Ackermann inversa	Complejidad amortizada por operación para la estructura de datos de conjunto disjunto
${\displaystyle O(\log \log n)}$	doble logarítmico	Número promedio de comparaciones realizadas para encontrar un elemento mediante la búsqueda por interpolación en una matriz ordenada de valores distribuidos uniformemente
${\displaystyle O(\log n)}$	logarítmico	Búsqueda de un elemento en una matriz ordenada con una búsqueda binaria o un árbol de búsqueda balanceado , así como todas las operaciones en un montón binomial
${\displaystyle O((\log n)^{c})}$ ${\textstyle c>1}$	polilogarítmico	El ordenamiento de cadenas de matrices se puede resolver en tiempo polilogarítmico en una máquina de acceso aleatorio paralelo .
${\displaystyle O(n^{c})}$ ${\textstyle 0<c<1}$	potencia fraccionaria	Buscando en un árbol kd
${\displaystyle O(n)}$	lineal	Encontrar un elemento en una lista desordenada o en una matriz desordenada; sumando dos enteros de n bits mediante acarreo de ondulación
${\displaystyle O(n\log ^{*}n)}$	n estrella logarítmica n	Realizar la triangulación de un polígono simple utilizando el algoritmo de Seidel , donde${\displaystyle \log ^{*}(n)={\begin{cases}0,&{\text{if }}n\leq 1\\1+\log ^{*}(\log n),&{\text{if }}n>1\end{cases}}}$
${\displaystyle O(n\log n)=O(\log n!)}$	linealítmico , loglineal, cuasilineal o " n log n "	Realización de una transformada rápida de Fourier ; ordenación por comparación más rápida posible ; ordenación por montículo y ordenación por combinación
${\displaystyle O(n^{2})}$	cuadrático	Multiplicación de dos números de n dígitos por la multiplicación de los libros escolares ; algoritmos de ordenamiento simples, como ordenamiento de burbuja , ordenamiento por selección y ordenamiento por inserción ; (en el peor de los casos) limitado a algunos algoritmos de ordenamiento generalmente más rápidos, como ordenamiento rápido , ordenamiento de Shell y ordenamiento de árbol
${\displaystyle O(n^{c})}$	polinomio o algebraico	Análisis gramatical de árboles adyacentes ; coincidencia máxima para gráficos bipartitos ; búsqueda del determinante con descomposición LU
${\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$ ${\textstyle 0<\alpha <1}$	Notación L o subexponencial	Factorizar un número utilizando la criba cuadrática o criba de cuerpo numérico
${\displaystyle O(c^{n})}$ ${\textstyle c>1}$	exponencial	Encontrar la solución (exacta) al problema del viajante de comercio mediante programación dinámica ; determinar si dos afirmaciones lógicas son equivalentes mediante búsqueda de fuerza bruta
${\displaystyle O(n!)}$	factorial	Solución del problema del viajante de comercio mediante búsqueda de fuerza bruta; generación de todas las permutaciones sin restricciones de un conjunto parcial ; búsqueda del determinante con expansión de Laplace ; enumeración de todas las particiones de un conjunto

El enunciado se debilita a veces para derivar fórmulas más simples para la complejidad asintótica. Para cualquier y , es un subconjunto de para cualquier , por lo que puede considerarse como un polinomio con un orden mayor.${\displaystyle f(n)=O(n!)}$${\displaystyle f(n)=O\left(n^{n}\right)}$${\displaystyle k>0}$${\displaystyle c>0}$ ${\displaystyle O(n^{c}(\log n)^{k})}$${\displaystyle O(n^{c+\varepsilon })}$${\displaystyle \varepsilon >0}$

La notación O grande se utiliza ampliamente en informática. Junto con otras notaciones relacionadas, forma la familia de notaciones de Bachmann-Landau. ^{[ cita requerida ]}

Intuitivamente, la afirmación " f ( x ) es o ( g ( x )) " (léase " f ( x ) es un poquito de g ( x ) " o " f ( x ) es de orden inferior a g ( x ) ") significa que g ( x ) crece mucho más rápido que f ( x ) o, equivalentemente, f ( x ) crece mucho más lento que g ( x ) . Como antes, sea f una función real o compleja y g una función real, ambas definidas en algún subconjunto no acotado de los números reales positivos , de modo que g ( x ) sea estrictamente positivo para todos los valores suficientemente grandes de x . Se escribe

${\displaystyle f(x)=o(g(x))\quad {\text{ as }}x\to \infty }$

si para cada constante positiva ε existe una constante tal que${\displaystyle x_{0}}$

${\displaystyle |f(x)|\leq \varepsilon g(x)\quad {\text{ for all }}x\geq x_{0}.}$^[16]

Por ejemplo, uno tiene

${\displaystyle 2x=o(x^{2})}$y     ambos como${\displaystyle 1/x=o(1),}$${\displaystyle x\to \infty .}$

La diferencia entre la definición de la notación O grande y la definición de O pequeña es que mientras que la primera tiene que ser verdadera para al menos una constante M , la segunda debe cumplirse para cada constante positiva ε , por pequeña que sea. ^[17] De esta manera, la notación O pequeña hace una declaración más fuerte que la notación O grande correspondiente: cada función que es O pequeña de g también es O grande de g , pero no cada función que es O grande de g es O pequeña de g . Por ejemplo, pero .${\displaystyle 2x^{2}=O(x^{2})}$${\displaystyle 2x^{2}\neq o(x^{2})}$

Si g ( x ) es distinto de cero, o al menos se vuelve distinto de cero más allá de cierto punto, la relación es equivalente a${\displaystyle f(x)=o(g(x))}$

${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0}$(y así es, de hecho, como Landau ^[16] definió originalmente la notación con o minúscula).

Little-o respeta una serie de operaciones aritméticas. Por ejemplo,

si c es una constante distinta de cero y entonces , y${\displaystyle f=o(g)}$${\displaystyle c\cdot f=o(g)}$

Si y entonces${\displaystyle f=o(F)}$${\displaystyle g=o(G)}$${\displaystyle f\cdot g=o(F\cdot G).}$

También satisface una relación de transitividad :

Si y entonces${\displaystyle f=o(g)}$${\displaystyle g=o(h)}$${\displaystyle f=o(h).}$

Otra notación asintótica es , que se lee "omega grande". ^[18] Hay dos definiciones generalizadas e incompatibles de la afirmación${\displaystyle \Omega }$

${\displaystyle f(x)=\Omega (g(x))}$como ,${\displaystyle x\to a}$

donde a es un número real, o , donde f y g son funciones reales definidas en un entorno de a , y donde g es positivo en este entorno.${\displaystyle \infty }$${\displaystyle -\infty }$

La definición de Hardy-Littlewood se utiliza principalmente en la teoría analítica de números , y la definición de Knuth principalmente en la teoría de la complejidad computacional ; las definiciones no son equivalentes.

En 1914, GH Hardy y JE Littlewood introdujeron el nuevo símbolo ^[19] que se define de la siguiente manera:${\displaystyle \ \Omega \ ,}$

${\displaystyle f(x)=\Omega {\bigl (}\ g(x)\ {\bigr )}\quad }$como si${\displaystyle \quad x\to \infty \quad }$${\displaystyle \quad \limsup _{x\to \infty }\ \left|{\frac {\ f(x)\ }{g(x)}}\right|>0~.}$

Así es la negación de${\displaystyle ~f(x)=\Omega {\bigl (}\ g(x)\ {\bigr )}~}$${\displaystyle ~f(x)=o{\bigl (}\ g(x)\ {\bigr )}~.}$

En 1916 los mismos autores introdujeron los dos nuevos símbolos y los definieron como: ^[20]${\displaystyle \ \Omega _{R}\ }$${\displaystyle \ \Omega _{L}\ ,}$

${\displaystyle f(x)=\Omega _{R}{\bigl (}\ g(x)\ {\bigr )}\quad }$como si${\displaystyle \quad x\to \infty \quad }$${\displaystyle \quad \limsup _{x\to \infty }\ {\frac {\ f(x)\ }{g(x)}}>0\ ;}$

${\displaystyle f(x)=\Omega _{L}{\bigl (}\ g(x)\ {\bigr )}\quad }$como si${\displaystyle \quad x\to \infty \quad }$${\displaystyle \quad ~\liminf _{x\to \infty }\ {\frac {\ f(x)\ }{g(x)}}<0~.}$

Estos símbolos fueron utilizados por E. Landau , con los mismos significados, en 1924. ^[21] Los autores que siguieron a Landau, sin embargo, utilizan una notación diferente para las mismas definiciones: ^{[ cita requerida ]} El símbolo ha sido reemplazado por la notación actual con la misma definición y se convirtió en${\displaystyle \ \Omega _{R}\ }$${\displaystyle \ \Omega _{+}\ }$${\displaystyle \ \Omega _{L}\ }$${\displaystyle \ \Omega _{-}~.}$

Estos tres símbolos, así como (lo que significa que tanto como se satisfacen), se utilizan actualmente en la teoría analítica de números . ^{[22] [23]}${\displaystyle \ \Omega \ ,\Omega _{+}\ ,\Omega _{-}\ ,}$${\displaystyle \ f(x)=\Omega _{\pm }{\bigl (}\ g(x)\ {\bigr )}\ }$${\displaystyle \ f(x)=\Omega _{+}{\bigl (}\ g(x)\ {\bigr )}\ }$${\displaystyle \ f(x)=\Omega _{-}{\bigl (}\ g(x)\ {\bigr )}\ }$

Tenemos

${\displaystyle \sin x=\Omega (1)\quad }$como${\displaystyle \quad x\to \infty \ ,}$

y más precisamente

${\displaystyle \sin x=\Omega _{\pm }(1)\quad }$como${\displaystyle \quad x\to \infty ~.}$

Tenemos

${\displaystyle 1+\sin x=\Omega (1)\quad }$como${\displaystyle \quad x\to \infty \ ,}$

y más precisamente

${\displaystyle 1+\sin x=\Omega _{+}(1)\quad }$como${\displaystyle \quad x\to \infty \ ;}$

sin embargo

${\displaystyle 1+\sin x\neq \Omega _{-}(1)\quad }$como${\displaystyle \quad x\to \infty ~.}$

En 1976, Donald Knuth publicó un artículo para justificar su uso del símbolo -para describir una propiedad más fuerte. ^[24] Knuth escribió: "Para todas las aplicaciones que he visto hasta ahora en informática, un requisito más fuerte... es mucho más apropiado". Definió${\displaystyle \Omega }$

${\displaystyle f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))}$

con el comentario: "Aunque he cambiado la definición de Hardy y Littlewood de , me siento justificado en hacerlo porque su definición no es de ninguna manera de uso amplio, y porque hay otras formas de decir lo que quieren decir en los casos comparativamente raros en que se aplica su definición". ^[24]${\displaystyle \Omega }$

Notación	Nombre [24]	Descripción	Definición formal	Definición de límite [25] [26] [27] [24] [19]
${\displaystyle f(n)=o(g(n))}$	O pequeña; Oh pequeña; O pequeña; Oh pequeña	f está dominada por g asintóticamente (para cualquier factor constante )${\displaystyle k}$	${\displaystyle \forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon |f(n)|\leq k\,g(n)}$	${\displaystyle \lim _{n\to \infty }{\frac {f(n)}{g(n)}}=0}$
${\displaystyle f(n)=O(g(n))}$	Gran O; Gran Oh; Gran Ómicron	${\displaystyle |f|}$está asintóticamente acotado por encima de g (hasta un factor constante )${\displaystyle k}$	${\displaystyle \exists k>0\,\exists n_{0}\,\forall n>n_{0}\colon |f(n)|\leq k\,g(n)}$	${\displaystyle \limsup _{n\to \infty }{\frac {f(n)}{g(n)}}<\infty }$
${\displaystyle f(n)\asymp g(n)}$(Notación de Hardy) o (notación de Knuth)${\displaystyle f(n)=\Theta (g(n))}$	Del mismo orden que (Hardy); Big Theta (Knuth)	f está asintóticamente acotado por g tanto por encima (con factor constante ) como por debajo (con factor constante )${\displaystyle k_{2}}$${\displaystyle k_{1}}$	${\displaystyle \exists k_{1}>0\,\exists k_{2}>0\,\exists n_{0}\,\forall n>n_{0}\colon }$ ${\displaystyle k_{1}\,g(n)\leq f(n)\leq k_{2}\,g(n)}$	${\displaystyle f(n)=O(g(n))}$y${\displaystyle g(n)=O(f(n))}$
${\displaystyle f(n)\sim g(n)}$	Equivalencia asintótica	f es igual a g asintóticamente	${\displaystyle \forall \varepsilon >0\,\exists n_{0}\,\forall n>n_{0}\colon \left|{\frac {f(n)}{g(n)}}-1\right|<\varepsilon }$	${\displaystyle \lim _{n\to \infty }{\frac {f(n)}{g(n)}}=1}$
${\displaystyle f(n)=\Omega (g(n))}$	El gran omega en la teoría de la complejidad (Knuth)	f está acotada inferiormente por g asintóticamente	${\displaystyle \exists k>0\,\exists n_{0}\,\forall n>n_{0}\colon f(n)\geq k\,g(n)}$	${\displaystyle \liminf _{n\to \infty }{\frac {f(n)}{g(n)}}>0}$
${\displaystyle f(n)=\omega (g(n))}$	Omega pequeño; Omega pequeño	f domina g asintóticamente	${\displaystyle \forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon f(n)>k\,g(n)}$	${\displaystyle \lim _{n\to \infty }{\frac {f(n)}{g(n)}}=\infty }$
${\displaystyle f(n)=\Omega (g(n))}$	El gran Omega en la teoría de números (Hardy-Littlewood)	${\displaystyle |f|}$no está dominado por g asintóticamente	${\displaystyle \exists k>0\,\forall n_{0}\,\exists n>n_{0}\colon |f(n)|\geq k\,g(n)}$	${\displaystyle \limsup _{n\to \infty }{\frac {\left|f(n)\right|}{g(n)}}>0}$

Las definiciones de límite suponen que es suficientemente grande . La tabla está (parcialmente) ordenada del más pequeño al más grande, en el sentido de que (la versión de Knuth de) en funciones corresponde a en la línea real ^[27] (la versión de Hardy–Littlewood de , sin embargo, no corresponde a ninguna descripción de este tipo).${\displaystyle g(n)>0}$${\displaystyle n}$${\displaystyle o,O,\Theta ,\sim ,}$${\displaystyle \Omega ,\omega }$${\displaystyle <,\leq ,\approx ,=,}$${\displaystyle \geq ,>}$${\displaystyle \Omega }$

La informática utiliza las notaciones big , big Theta , little , little omega y la notación big Omega de Knuth . ^[28] La teoría analítica de números a menudo utiliza las notaciones big , small , Hardy's , ^[29] Hardy–Littlewood big Omega (con o sin los subíndices +, − o ±) y . ^[22] La notación small omega no se utiliza tan a menudo en el análisis. ^[30]${\displaystyle O}$${\displaystyle \Theta }$${\displaystyle o}$${\displaystyle \omega }$${\displaystyle \Omega }$${\displaystyle O}$${\displaystyle o}$${\displaystyle \asymp }$${\displaystyle \Omega }$${\displaystyle \sim }$${\displaystyle \omega }$

De manera informal, especialmente en informática, la notación O grande a menudo se puede usar de manera algo diferente para describir un límite asintótico estricto , donde el uso de la notación Theta Θ grande puede ser más apropiado en un contexto dado. ^[31] Por ejemplo, al considerar una función T ( n ) = 73 n ³ + 22 n ² + 58, todas las siguientes son generalmente aceptables, pero los límites más estrictos (como los números 2 y 3 a continuación) generalmente se prefieren fuertemente sobre los límites más flexibles (como el número 1 a continuación).

1. T ( n ) = O ( n100 ⁾
2. T ( n ) = O ( n3 ⁾
3. T ( n ) = Θ( n3 ⁾

Las afirmaciones equivalentes en inglés son respectivamente:

1. T ( n ) crece asintóticamente no más rápido que n ¹⁰⁰
2. T ( n ) crece asintóticamente no más rápido que n ³
3. T ( n ) crece asintóticamente tan rápido como n ³ .

Por lo tanto, si bien las tres afirmaciones son verdaderas, cada vez se incluye más información en cada una de ellas. Sin embargo, en algunos campos, la notación O mayúscula (número 2 en las listas anteriores) se usaría con más frecuencia que la notación Theta mayúscula (elementos numerados 3 en las listas anteriores). Por ejemplo, si T ( n ) representa el tiempo de ejecución de un algoritmo recientemente desarrollado para un tamaño de entrada n , los inventores y usuarios del algoritmo podrían estar más inclinados a establecer un límite asintótico superior sobre cuánto tiempo tomará ejecutarse sin hacer una declaración explícita sobre el límite asintótico inferior.

En su libro Introducción a los algoritmos , Cormen , Leiserson , Rivest y Stein consideran el conjunto de funciones f que satisfacen

${\displaystyle f(n)=O(g(n))\quad (n\to \infty )~.}$

En una notación correcta, este conjunto puede, por ejemplo, llamarse O ( g ), donde

$${\displaystyle O(g)=\{f:{\text{there exist positive constants}}~c~{\text{and}}~n_{0}~{\text{such that}}~0\leq f(n)\leq cg(n){\text{ for all }}n\geq n_{0}\}.}$$^[32]

Los autores afirman que el uso del operador de igualdad (=) para denotar la pertenencia a un conjunto en lugar del operador de pertenencia a un conjunto (∈) es un abuso de la notación, pero que hacerlo tiene ventajas. ^[6] Dentro de una ecuación o desigualdad, el uso de la notación asintótica representa una función anónima en el conjunto O ( g ), que elimina los términos de orden inferior y ayuda a reducir el desorden innecesario en las ecuaciones, por ejemplo: ^[33]

${\displaystyle 2n^{2}+3n+1=2n^{2}+O(n).}$

Otra notación que a veces se utiliza en informática es Õ (léase soft-O ), que oculta factores polilogarítmicos. Hay dos definiciones en uso: algunos autores utilizan f ( n ) =  Õ ( g ( n )) como abreviatura de f ( n ) = O ( g ( n ) log ^k n ) para algún k , mientras que otros la utilizan como abreviatura de f ( n ) = O ( g ( n ) log ^k g ( n )) . ^[34] Cuando g ( n ) es polinomial en n , no hay diferencia; sin embargo, la última definición permite decir, por ejemplo, que mientras que la primera definición permite para cualquier constante k . Algunos autores escriben O ^* con el mismo propósito que la última definición. ^[35] Básicamente, se trata de una notación O grande , que ignora los factores logarítmicos porque los efectos de la tasa de crecimiento de alguna otra función superlogarítmica indican una explosión de la tasa de crecimiento para parámetros de entrada de gran tamaño que es más importante para predecir un mal rendimiento en tiempo de ejecución que los efectos de punto más fino aportados por el factor o factores de crecimiento logarítmico. Esta notación se utiliza a menudo para obviar la "critica" dentro de las tasas de crecimiento que se indican como demasiado estrechamente limitadas para los asuntos en cuestión (ya que log ^k n es siempre o ( n ^ε ) para cualquier constante k y cualquier ε > 0 ).${\displaystyle n2^{n}={\tilde {O}}(2^{n})}$${\displaystyle \log ^{k}n={\tilde {O}}(1)}$ 

Además, la notación L , definida como

${\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }},}$

es conveniente para funciones que están entre polinómicas y exponenciales en términos de .${\displaystyle \ln n}$

La generalización a funciones que toman valores en cualquier espacio vectorial normado es sencilla (reemplazando valores absolutos por normas), donde f y g no necesitan tomar sus valores en el mismo espacio. También es posible una generalización a funciones g que toman valores en cualquier grupo topológico ^{[ cita requerida ]} . El "proceso limitante" x → x _o también se puede generalizar introduciendo una base de filtro arbitraria, es decir, a redes dirigidas f y  g . La notación o se puede utilizar para definir derivadas y diferenciabilidad en espacios bastante generales, y también equivalencia (asintótica) de funciones,

${\displaystyle f\sim g\iff (f-g)\in o(g)}$

que es una relación de equivalencia y una noción más restrictiva que la relación " f es Θ( g )" de arriba. (Se reduce a lim f / g = 1 si f y g son funciones reales positivas). Por ejemplo, 2 x es Θ( x ), pero 2 x − x no es o ( x ).

El símbolo O fue introducido por primera vez por el teórico de números Paul Bachmann en 1894, en el segundo volumen de su libro Analytische Zahlentheorie (" teoría analítica de números "). ^[1] El teórico de números Edmund Landau lo adoptó, y así se inspiró para introducir en 1909 la notación o; ^[2] por lo que ahora ambos se llaman símbolos de Landau. Estas notaciones se utilizaron en matemáticas aplicadas durante la década de 1950 para el análisis asintótico. ^[36] El símbolo (en el sentido de "no es una o de") fue introducido en 1914 por Hardy y Littlewood. ^[19] Hardy y Littlewood también introdujeron en 1916 los símbolos ("derecha") e ("izquierda"), ^[20] precursores de los símbolos modernos ("no es menor que una o minúscula de") y ("no es mayor que una o minúscula de"). Por lo tanto, los símbolos Omega (con sus significados originales) a veces también se denominan "símbolos de Landau". Esta notación se empezó a utilizar comúnmente en la teoría de números al menos desde la década de 1950. ^[37]${\displaystyle \Omega }$${\displaystyle \Omega _{R}}$${\displaystyle \Omega _{L}}$${\displaystyle \Omega _{+}}$${\displaystyle \Omega _{-}}$${\displaystyle \Omega }$

El símbolo , aunque había sido usado antes con diferentes significados, ^[27] recibió su definición moderna por Landau en 1909 ^[38] y por Hardy en 1910. ^[39] Justo arriba en la misma página de su tratado Hardy definió el símbolo , donde significa que tanto como se satisfacen. La notación todavía se usa actualmente en la teoría analítica de números. ^{[40] [29]} En su tratado Hardy también propuso el símbolo , donde significa que para alguna constante .${\displaystyle \sim }$${\displaystyle \asymp }$${\displaystyle f(x)\asymp g(x)}$${\displaystyle f(x)=O(g(x))}$${\displaystyle g(x)=O(f(x))}$${\displaystyle \,\asymp \!\!\!\!\!\!-}$${\displaystyle f\asymp \!\!\!\!\!\!-g}$${\displaystyle f\sim Kg}$${\displaystyle K\not =0}$

En la década de 1970, la gran O fue popularizada en la ciencia informática por Donald Knuth , quien propuso una notación diferente para Hardy y propuso una definición diferente para la notación Omega de Hardy y Littlewood. ^[24]${\displaystyle f(x)=\Theta (g(x))}$${\displaystyle f(x)\asymp g(x)}$

Otros dos símbolos acuñados por Hardy fueron (en términos de la notación O moderna)

${\displaystyle f\preccurlyeq g\iff f=O(g)}$   y   ${\displaystyle f\prec g\iff f=o(g);}$

(Sin embargo, Hardy nunca definió ni utilizó la notación , ni , como se ha informado a veces). Hardy introdujo los símbolos y (así como los otros símbolos ya mencionados) en su tratado de 1910 "Órdenes del infinito", y los utilizó solo en tres artículos (1910-1913). En sus casi 400 artículos y libros restantes utilizó sistemáticamente los símbolos de Landau O y o.${\displaystyle \prec \!\!\prec }$${\displaystyle \ll }$${\displaystyle \preccurlyeq }$${\displaystyle \prec }$

Los símbolos de Hardy y (así como ) ya no se utilizan. Por otro lado, en la década de 1930, ^[41] el teórico de números ruso Ivan Matveyevich Vinogradov introdujo su notación , que se ha utilizado cada vez más en la teoría de números en lugar de la notación . Tenemos${\displaystyle \preccurlyeq }$${\displaystyle \prec }$${\displaystyle \,\asymp \!\!\!\!\!\!-}$${\displaystyle \ll }$${\displaystyle O}$

${\displaystyle f\ll g\iff f=O(g),}$

y con frecuencia se utilizan ambas notaciones en el mismo artículo.

La O mayúscula originalmente significaba "orden de" ("Ordnung", Bachmann 1894), y por lo tanto es una letra latina. Ni Bachmann ni Landau la llamaron nunca "ómicron". Mucho más tarde (1976) Knuth consideró que el símbolo era un ómicron mayúscula , ^[24] probablemente en referencia a su definición del símbolo Omega . El dígito cero no debería utilizarse.

• Complejidad computacional asintótica
• Expansión asintótica : aproximación de funciones generalizando la fórmula de Taylor
• Algoritmo asintóticamente óptimo : frase que se utiliza con frecuencia para describir un algoritmo que tiene un límite superior asintóticamente dentro de una constante de un límite inferior para el problema.
• O grande en notación de probabilidad : O _p , o _p
• Límite inferior y límite superior : una explicación de algunas de las notaciones de límite utilizadas en este artículo
• Teorema maestro (análisis de algoritmos) : para analizar algoritmos recursivos de divide y vencerás utilizando la notación Big O
• Teorema de Nachbin : Un método preciso para acotar funciones analíticas complejas de modo que se pueda establecer el dominio de convergencia de las transformadas integrales.
• Orden de aproximación
• Complejidad computacional de operaciones matemáticas

• Hardy, GH (1910). Órdenes del infinito: el «cálculo del infinito» de Paul du Bois-Reymond. Cambridge University Press .
• Knuth, Donald (1997). "1.2.11: Representaciones asintóticas". Algoritmos fundamentales . El arte de la programación informática. Vol. 1 (3.ª ed.). Addison-Wesley. ISBN 978-0-201-89683-1.
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). "3.1: Notación asintótica". Introducción a los algoritmos (2.ª ed.). MIT Press y McGraw-Hill. ISBN 978-0-262-03293-3.
• Sipser, Michael (1997). Introducción a la teoría de la computación . PWS Publishing. pp. 226–228. ISBN 978-0-534-94728-6.
• Avigad, Jeremy; Donnelly, Kevin (2004). Formalización de la notación O en Isabelle/HOL (PDF) . Conferencia conjunta internacional sobre razonamiento automatizado. doi :10.1007/978-3-540-25984-8_27.
• Black, Paul E. (11 de marzo de 2005). Black, Paul E. (ed.). "big-O notation". Dictionary of Algorithms and Data Structures . Instituto Nacional de Estándares y Tecnología de Estados Unidos . Consultado el 16 de diciembre de 2006 .
• Black, Paul E. (17 de diciembre de 2004). Black, Paul E. (ed.). "little-o notation". Dictionary of Algorithms and Data Structures . Instituto Nacional de Estándares y Tecnología de Estados Unidos . Consultado el 16 de diciembre de 2006 .
• Black, Paul E. (17 de diciembre de 2004). Black, Paul E. (ed.). "Ω". Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología de Estados Unidos . Consultado el 16 de diciembre de 2006 .
• Black, Paul E. (17 de diciembre de 2004). Black, Paul E. (ed.). "ω". Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología de Estados Unidos . Consultado el 16 de diciembre de 2006 .
• Black, Paul E. (17 de diciembre de 2004). Black, Paul E. (ed.). "Θ". Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología de Estados Unidos . Consultado el 16 de diciembre de 2006 .