Notación Big O

La notación Big O es una notación matemática que describe el tamaño aproximado de una función en un dominio . Big O pertenece a una familia de notaciones inventadas por los matemáticos alemanes Paul Bachmann ^{[ 1 ]} y Edmund Landau ^{[ 2 ]} y ampliadas por otros, conocidas colectivamente como notación Bachmann-Landau . La letra O significa Ordnung , es decir, el orden de aproximación .

En ciencias de la computación , la notación O grande se utiliza para clasificar algoritmos según cómo sus requisitos de tiempo de ejecución o espacio ^{[ a ]} crecen con la entrada. ^{[ 3 ]} En teoría analítica de números , la notación O grande expresa límites en el crecimiento de una función aritmética , como para el término restante en el teorema de los números primos . ^{[ 4 ]} En análisis matemático , incluido el cálculo , la notación O grande limita el error al truncar una serie de potencias y expresa la calidad de aproximación de una función de valor real o complejo por una función más simple.

A menudo, la notación O mayúscula caracteriza las funciones según su tasa de crecimiento a medida que la variable aumenta: diferentes funciones con la misma tasa de crecimiento asintótico pueden representarse con la misma notación O. La letra O se utiliza porque la tasa de crecimiento de una función también se conoce como su orden . La descripción de una función mediante la notación O mayúscula solo proporciona una cota superior para su tasa de crecimiento.

Asociadas a la notación de la gran O existen varias notaciones relacionadas, que utilizan los símbolos , , , , , , , y para describir otros tipos de límites en las tasas de crecimiento. ^{[ 5 ] [ 6 ] [ 7 ] [ 8 ]}${\displaystyle o}$${\displaystyle \sim }$${\displaystyle \Omega }$${\displaystyle \ll }$${\displaystyle \gg }$${\displaystyle \asymp }$${\displaystyle \omega }$${\displaystyle \Theta }$

Bachmann propuso la notación en 1894 y Landau la amplió en 1909. Una notación anterior fue propuesta por Paul du Bois-Reymond en 1870. ^{[ 9 ]}

Let ${\textstyle f,}$ the function to be estimated, be either a real or complex valued function defined on a domain${\textstyle D,}$ and let ${\textstyle g,}$ the comparison function, be a non-negative real valued function defined on the same set ${\textstyle D.}$ Common choices for the domain are intervals of real numbers, bounded or unbounded, the set of positive integers, the set of complex numbers and tuples of real/complex numbers. With the domain written explicitly or understood implicitly, one writes

$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\ }$$

which is read as "${\textstyle f(x)}$ is big ${\textstyle O}$ of ${\textstyle g(x)}$" if there exists a positive real number ${\textstyle M}$ such that

$${\displaystyle \left|f(x)\right|\leq M\ g(x)\qquad ~{\mathsf {\ para\ todo\ }}~\quad x\in D.}$$

If ${\displaystyle g(x)>0}$ (i.e. g is also never zero) throughout the domain ${\displaystyle D,}$ an equivalent definition is that the ratio ${\textstyle {\frac {f(x)}{g(x)}}}$ is bounded, i.e. there is a positive real number ${\displaystyle M}$ so that ${\textstyle {\Big |}{\frac {f(x)}{g(x)}}{\Big |}\leq M}$ for all ${\displaystyle x\in D.}$ These encompass all the uses of big ${\textstyle O}$ in computer science and mathematics, including its use where the domain is finite, infinite, real, complex, single variate, or multivariate. In most applications, one chooses the function ${\displaystyle g(x)}$ appearing within the argument of ${\textstyle O{\bigl (}\cdot {\bigr )}}$ to be as simple a form as possible, omitting constant factors and lower order terms. The number ${\textstyle M}$ is called the implied constant because it is normally not specified. When using big ${\textstyle O}$ notation, what matters is that some finite ${\displaystyle M}$ exists, not its specific value. This simplifies the presentation of many analytic inequalities.

For functions defined on positive real numbers or positive integers, a more restrictive and somewhat conflicting definition is still in common use,^[3][10] especially in computer science. When restricted to functions which are eventually positive, the notation

$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\qquad ~{\mathsf {cuando}}\quad x\to \infty }$$

means that for some real number ${\textstyle a,}$${\textstyle f(x)=O{\bigl (}g(x){\bigr )}}$ in the domain ${\textstyle \left[a,\infty \right).}$ Here, the expression ${\textstyle x\to \infty }$ does not indicate a limit, but the notion that the inequality holds for large enough${\textstyle x.}$ The expression ${\textstyle x\to \infty }$ often is omitted.^[3]

Similarly, for a real number ${\textstyle a,}$ the notation

$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\qquad ~{\text{ cuando }}\ x\to a}$$

means that for some constant ${\textstyle c>0,}$${\textstyle f(x)=O{\bigl (}g(x){\bigr )}}$ on the interval ${\displaystyle \left[ac,a+c\right];}$ that is, in a small neighborhood of ${\displaystyle a.}$ In addition, the notation $${\displaystyle \ f(x)=h(x)+O{\bigl (}g(x){\bigr )}\ }$$ means ${\textstyle f(x)-h(x)=O{\bigl (}g(x){\bigr )}.}$More complicated expressions are also possible.

A pesar de la presencia del signo igual ( = ) tal como está escrito, la expresión no se refiere a una igualdad , sino más bien a una desigualdad que relaciona y${\textstyle f(x)=O{\bigl (}g(x){\bigr )}}$${\textstyle f}$${\textstyle g.}$

En la década de 1930, ^{[ 6 ]} el teórico de números ruso IM Vinogradov introdujo la notación que se ha utilizado cada vez más en la teoría de números ^{[ 4 ] [ 11 ] [ 12 ]} y otras ramas de las matemáticas, como una alternativa a la notación. Tenemos ${\displaystyle \ll ,}$${\textstyle O}$

$${\displaystyle \ f\ll g\iff f=O{\bigl (}g{\bigr )}.}$$

Con frecuencia, ambas notaciones se utilizan en la misma obra.

En informática ^{[ 3 ]} es común definir grande${\textstyle O}$ como también un conjunto de funciones. Con la función positiva (o no negativa) especificada, se interpreta como que representa el conjunto de todas las funciones que satisfacen Entonces se puede escribir equivalentemente como "la función está entre el conjunto de todas las funciones de orden como máximo "${\displaystyle g(x)}$${\textstyle O{\bigl (}g(x){\bigr )}}$${\textstyle {\tilde {f}}}$${\textstyle {\tilde {f}}(x)=O{\bigl (}g(x){\bigr )}.}$${\textstyle f(x)\in O{\bigl (}g(x){\bigr )},}$${\textstyle \ f(x)\ }$${\textstyle g(x).}$

En el uso típico, la notación se aplica a un intervalo infinito de números reales y captura el comportamiento de la función para valores muy grandes de . En este contexto, la contribución de los términos que crecen "más rápidamente" eventualmente hará que los demás sean irrelevantes. Como resultado, se pueden aplicar las siguientes reglas de simplificación: ${\displaystyle O}$${\displaystyle [a,\infty )}$${\displaystyle x}$

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

Por ejemplo, sea , y supongamos que deseamos simplificar esta función, usando notación, para describir su tasa de crecimiento para valores grandes de . Esta función es la suma de tres términos: , , y . De estos tres términos, el que tiene la tasa de crecimiento más alta es el que tiene el mayor exponente como función de , es decir . Ahora se puede aplicar la segunda regla: es un producto de y en el que el primer factor no depende de . Omitiendo este factor se obtiene la forma simplificada . Por lo tanto, decimos que es una "O grande" de . Matemáticamente, podemos escribir para todo . Se puede confirmar este cálculo usando la definición formal: sea y . Aplicando la definición formal anterior, la afirmación de que es equivalente a su expansión, para alguna elección adecuada de un número real positivo y para todo . Para probar esto, sea . Entonces, para todo : por lo que Si bien también es cierto, por el mismo argumento, que , esta es una aproximación menos precisa de la función . Por otro lado, la afirmación es falsa, porque el término hace que sea ilimitado. ${\displaystyle f(x)=6x^{4}-2x^{3}+5}$${\displaystyle O}$${\displaystyle x}$${\displaystyle 6x^{4}}$${\displaystyle -2x^{3}}$${\displaystyle 5}$${\displaystyle x}$${\displaystyle 6x^{4}}$${\displaystyle 6x^{4}}$${\displaystyle 6}$${\displaystyle x^{4}}$${\displaystyle x}$${\displaystyle x^{4}}$${\displaystyle f(x)}$${\displaystyle x^{4}}$${\displaystyle f(x)=O(x^{4})}$${\displaystyle x\geq 1}$${\displaystyle f(x)=6x^{4}-2x^{3}+5}$${\displaystyle g(x)=x^{4}}$${\displaystyle f(x)=O(x^{4})}$$${\displaystyle |f(x)|\leq Mx^{4}}$$${\displaystyle M}$${\displaystyle x\geq 1}$${\displaystyle M=13}$${\displaystyle x\geq 1}$$${\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}.}$$${\displaystyle f(x)=O(x^{10})}$${\displaystyle f}$${\displaystyle f(x)=O(x^{3})}$${\displaystyle 6x^{4}}$${\displaystyle f(x)/x^{3}}$

Cuando una función describe el número de pasos necesarios en un algoritmo con entrada , una expresión como con el dominio implícito siendo el conjunto de enteros positivos, puede interpretarse como que el algoritmo tiene como máximo el orden de complejidad temporal. ${\displaystyle T(n)}$${\displaystyle n}$$${\displaystyle T(n)=O(n^{2})}$$${\displaystyle n^{2}}$

La notación Big O también se puede usar para describir el término de error en una aproximación a una función matemática en un intervalo finito. Los términos más significativos se escriben explícitamente, y luego los menos significativos se resumen en un solo término Big O. Consideremos, por ejemplo, la serie exponencial y dos expresiones de la misma que son válidas cuando es pequeño: La expresión del medio ( la línea con " " ) significa que el valor absoluto del error es como máximo una constante veces cuando es pequeño. Este es un ejemplo del uso del teorema de Taylor . ${\displaystyle x}$$${\displaystyle {\begin{aligned}e^{x}&=1+x+{\frac {\;x^{2}\ }{2!}}+{\frac {\;x^{3}\ }{3!}}+{\frac {\;x^{4}\ }{4!}}+\dotsb &&{\text{ para todo }}x finito\\[4pt]&=1+x+{\frac {\;x^{2}\ }{2}}+O(|x|^{3})&&{\text{ para todo }}|x|\leq 1\\[4pt]&=1+x+O(x^{2})&&{\text{ para todo }}|x|\leq 1.\end{aligned}}}$$${\displaystyle O(|x^{3}|)}$${\displaystyle \ e^{x}-(1+x+{\frac {\;x^{2}\ }{2}})\ }$${\displaystyle ~|x^{3}|\ }$${\displaystyle \ x~}$

El comportamiento de una función dada puede ser muy diferente en dominios finitos que en dominios infinitos, por ejemplo, mientras que $${\displaystyle (x+1)^{8}=x^{8}+O(x^{7})\quad {\text{ para }}x\geq 1}$$$${\displaystyle (x+1)^{8}=1+8x+O(x^{2})\quad {\text{ para }}|x|\leq 1.}$$

$${\displaystyle x\sin y=O(x)\quad {\text{ para }}x\geq 1,y{\text{ cualquier número real}}}$$

$${\displaystyle 3a^{2}+7ab+2b^{2}+a+3b+14\ll a^{2}+b^{2}\ll a^{2}\quad {\text{ for all }}a\geq b\geq 1}$$

$${\displaystyle {\frac {xy}{x^{2}+y^{2}}}=O(1)\quad {\text{ for all real }}x,y{\text{ that are not both }}0}$$

$${\displaystyle x^{it}=O(1)\quad {\text{ for }}x\neq 0,t\in \mathbb {R} .}$$

Aquí tenemos una función de variable compleja de dos variables. En general, cualquier función acotada es . ${\displaystyle O(1)}$

$${\displaystyle (x+y)^{10}=O(x^{10})\quad {\text{ for }}x\geq 1,-2\leq y\leq 2.}$$

El último ejemplo ilustra una mezcla de dominios finitos e infinitos en las diferentes variables.

En todos estos ejemplos, el límite es uniforme en ambas variables. A veces, en una expresión multivariable, una variable es más importante que las demás, y se puede expresar que la constante implícita depende de una o más de las variables usando subíndices al símbolo O mayúscula o al símbolo. Por ejemplo, considérese la expresión ${\displaystyle M}$${\displaystyle \ll }$

$${\displaystyle (1+x)^{b}=1+O_{b}(x)\quad {\text{ for }}0\leq x\leq 1,b{\text{ any real number.}}}$$

Esto significa que para cada número real , hay una constante , que depende de , de modo que para todo , Esta afirmación particular se deduce del teorema general del binomio . ${\displaystyle b}$${\displaystyle M_{b}}$${\displaystyle b}$${\displaystyle 0\leq x\leq 1}$$${\displaystyle |(1+x)^{b}-1|\leq M_{b}\cdot x.}$$

Otro ejemplo, común en la teoría de las series de Taylor , es Aquí la constante implícita depende del tamaño del dominio. $${\displaystyle e^{x}=1+x+O_{r}(x^{2})\quad {\text{ for all }}|x|\leq r,r{\text{ being any real number.}}}$$

La convención de subíndices se aplica a todas las demás notaciones de esta página.

${\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(|f|g)}$

Si y entonces . Se deduce que si y entonces . ${\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}=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).}$

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

Si la función de un entero positivo se puede escribir como una suma finita de otras funciones, entonces la que crece más rápido determina el orden de . Por ejemplo, ${\displaystyle f}$${\displaystyle n}$${\displaystyle f(n)}$

${\displaystyle f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{for }}n\geq 1.}$

Algunas reglas generales sobre el crecimiento hacia el infinito ; la segunda y tercera propiedad que se mencionan a continuación se pueden demostrar rigurosamente utilizando la regla de L'Hôpital :

Para , entonces como . ${\displaystyle b\geq a}$$${\displaystyle n^{a}=O(n^{b})}$$${\displaystyle n\to \infty }$

Para cualquier valor positivo, sin importar cuán grande o pequeño sea. Aquí, la constante implícita depende tanto de como de . ${\displaystyle a,b,}$$${\displaystyle (\log n)^{a}=O_{a,b}(n^{b}),}$$${\displaystyle a}$${\displaystyle b}$${\displaystyle a}$${\displaystyle b}$

Para cualquier cosa positiva, sin importar cuán grande o pequeña sea. ${\displaystyle a,b,}$$${\displaystyle n^{a}=O_{a,b}(e^{bn}),}$$${\displaystyle a}$${\displaystyle b}$

Una función que crece más rápido que cualquier se llama superpolinomial . Una que crece más lentamente que cualquier función exponencial de la forma con se llama subexponencial . Un algoritmo puede requerir un tiempo que sea a la vez superpolinomial y subexponencial; ejemplos de esto incluyen los algoritmos más rápidos conocidos para la factorización de enteros y la función . ${\displaystyle n^{c}}$${\displaystyle c}$${\displaystyle c^{n}}$${\displaystyle c>1}$${\displaystyle n^{\log n}}$

Podemos ignorar cualquier potencia de dentro de los logaritmos. Para cualquier positivo , la notación significa exactamente lo mismo que , ya que . De manera similar, los logaritmos con bases constantes diferentes son equivalentes con respecto a la notación Big O. Por otro lado, las exponenciales con bases diferentes no son del mismo orden. Por ejemplo, y no son del mismo orden. ${\displaystyle n}$${\displaystyle c}$${\displaystyle O(\log n)}$${\displaystyle O(\log(n^{c}))}$${\displaystyle \log(n^{c})=c\log n}$${\displaystyle 2^{n}}$${\displaystyle 3^{n}}$

En un uso más complejo, puede aparecer en diferentes lugares de una ecuación, incluso varias veces en cada lado. Por ejemplo, las siguientes afirmaciones son verdaderas para un entero positivo: El significado de tales afirmaciones es el siguiente: para cualquier función que satisfaga cada una en el lado izquierdo, hay algunas funciones que satisfacen cada una en el lado derecho, de modo que al sustituir todas estas funciones en la ecuación se igualan ambos lados. Por ejemplo, la tercera ecuación anterior significa: "Para cualquier función que satisfaga , hay alguna función tal que ". La constante implícita en la afirmación " " puede depender de la constante implícita en la expresión " ". ${\displaystyle O(\cdot )}$${\displaystyle n}$$${\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}}}$$${\displaystyle O(\cdot )}$${\displaystyle O(\cdot )}$${\displaystyle f(n)=O(1)}$${\displaystyle g(n)=O(e^{n})}$${\displaystyle n^{f(n)}=g(n)}$${\displaystyle g(n)=O(e^{n})}$${\displaystyle f(n)=O(1)}$

Algunos ejemplos adicionales: $${\displaystyle {\begin{aligned}f=O(g)\;&\Rightarrow \;\int _{a}^{b}f=O{\bigg (}\int _{a}^{b}g{\bigg )}\\f(x)=g(x)+O(1)\;&\Rightarrow \;e^{f(x)}=O(e^{g(x)})\\(1+O(1/x))^{O(x)}&=O(1)\quad {\text{ for }}x>0\\\sin x&=O(|x|)\quad {\text{ for all real }}x.\end{aligned}}}$$

Cuando ambas son funciones positivas, Vinogradov ^{[ 6 ]} introdujo la notación , que significa lo mismo que . Las dos notaciones de Vinogradov gozan de simetría visual, ya que para funciones positivas , tenemos ${\displaystyle f,g}$${\displaystyle f(x)\gg g(x)}$${\displaystyle g(x)=O(f(x))}$${\displaystyle f,g}$$${\displaystyle f(x)\ll g(x)\Longleftrightarrow g(x)\gg f(x).}$$

En 1976, Donald Knuth ^{[ 8 ]} definió

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

que tiene el mismo significado que el de Vinogradov . ${\displaystyle f(x)\gg g(x)}$

Sin embargo, mucho antes, Hardy y Littlewood ^{[ 7 ]} habían definido de manera diferente , y su notación goza de un uso generalizado hoy en día en la teoría analítica de números. ^{[ 13 ] [ 11 ] [ 12 ]} Justificando su uso del símbolo - para describir una propiedad más fuerte, ^{[ 8 ]} Knuth escribió: "Para todas las aplicaciones que he visto hasta ahora en ciencias de la computación, un requisito más fuerte... es mucho más apropiado". Knuth escribió además: "Aunque he cambiado la definición de Hardy y Littlewood de , me siento justificado al hacerlo porque su definición no es de ninguna manera de uso generalizado, y porque hay otras maneras de decir lo que quieren decir en los casos comparativamente raros en los que se aplica su definición". ^{[ 8 ]} El gran de Knuth goza de un uso generalizado hoy en día en ciencias de la computación y combinatoria. ${\displaystyle \Omega }$${\displaystyle \Omega }$${\displaystyle \Omega }$${\displaystyle \Omega }$

In analytic number theory,^[12] the notation ${\displaystyle f(x)\asymp g(x)}$ means both ${\displaystyle f(x)=O(g(x))}$ and ${\displaystyle g(x)=O(f(x))}$. This notation is originally due to Hardy.^[5] Knuth's notation for the same notion is ${\displaystyle f(x)=\Theta (g(x))}$.^[8] Roughly speaking, these statements assert that ${\displaystyle f(x)}$ and ${\displaystyle g(x)}$ have the same order. These notations mean that there are positive constants ${\displaystyle M,N}$ so that $${\displaystyle Ng(x)\leq f(x)\leq Mg(x)}$$ for all ${\displaystyle x}$ in the common domain of ${\displaystyle f,g}$. When the functions are defined on the positive integers or positive real numbers, as with big O, writers oftentimes interpret statements ${\displaystyle f(x)=\Omega (g(x))}$ and ${\displaystyle f(x)=\Theta (g(x))}$ as holding for all sufficiently large ${\displaystyle x}$, that is, for all ${\displaystyle x}$ beyond some point ${\displaystyle x_{0}}$. Sometimes this is indicated by appending ${\displaystyle x\to \infty }$ to the statement. For example, $${\displaystyle 2n^{2}-10n=\Theta (n^{2})}$$ is true for the domain ${\displaystyle n\geq 6}$ but false if the domain is all positive integers, since the function is zero at ${\displaystyle n=5}$.

$${\displaystyle n^{3}+20n^{2}+n+12\asymp n^{3}\quad {\text{ for all }}n\geq 1.}$$

$${\displaystyle (1+x)^{8}=x^{8}+\Theta (x^{7})\quad {\text{ for all }}x\geq 1.}$$

The notation

$${\displaystyle f(n)=e^{\Omega (n)}\quad {\text{ for all }}n\geq 1,}$$ means that there is a positive constant ${\displaystyle M}$ so that ${\displaystyle f(n)\geq e^{Mn}}$ for all ${\displaystyle n\geq 1}$. By contrast, $${\displaystyle f(n)=e^{-O(n)}\quad {\text{ for all }}n\geq 1,}$$ means that there is a positive constant ${\displaystyle M}$ so that ${\displaystyle f(n)\geq e^{-Mn}}$ for all ${\displaystyle n\geq 1}$ and $${\displaystyle f(n)=e^{\Theta (n)}\quad {\text{ for all }}n\geq 1,}$$ means that there are positive constants ${\displaystyle M,N}$ so that ${\displaystyle e^{Mn}\leq f(n)\leq e^{Nn}}$ for all ${\displaystyle n\geq 1}$.

For any domain ${\displaystyle D}$, $${\displaystyle f(x)=g(x)+O(1)\Longleftrightarrow e^{f(x)}\asymp e^{g(x)},}$$ each statement being for all ${\displaystyle x}$ in ${\displaystyle D}$.

Here is a list of classes of functions that are commonly encountered when analyzing the running time of an algorithm. In each case, c is a positive constant and n increases without bound. The slower-growing functions are generally listed first.

La afirmación a veces se debilita para derivar fórmulas más simples para la complejidad asintótica. En muchos de estos ejemplos, el tiempo de ejecución es en realidad , lo que transmite mayor precisión. ${\displaystyle f(n)=O(n!)}$${\displaystyle f(n)=O\left(n^{n}\right)}$${\displaystyle \Theta (g(n))}$

Para funciones de valor real o complejo de una variable real con suficientemente grande , se escribe ^{[ 2 ]}${\displaystyle x}$${\displaystyle g(x)>0}$${\displaystyle x}$

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

Si es decir, para cada constante positiva ε existe una constante tal que $${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0.}$$${\displaystyle x_{0}}$

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

Intuitivamente, esto significa que crece mucho más rápido que , o equivalentemente crece mucho más lento que . Por ejemplo, se tiene ${\displaystyle g(x)}$${\displaystyle f(x)}$${\displaystyle f(x)}$${\displaystyle g(x)}$

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

When one is interested in the behavior of a function for large values of ${\displaystyle x}$, little-o notation makes a stronger statement than the corresponding big-O notation: every function that is little-o of ${\displaystyle g}$ is also big-O of ${\displaystyle g}$ on some interval ${\displaystyle [a,\infty )}$, but not every function that is big-O of ${\displaystyle g}$ is little-o of ${\displaystyle g}$. For example, ${\displaystyle 2x^{2}=O(x^{2})}$ but ${\displaystyle 2x^{2}\neq o(x^{2})}$ for ${\displaystyle x\geq 1}$.

Little-o respects a number of arithmetic operations. For example,

if ${\displaystyle c}$ is a nonzero constant and ${\displaystyle f=o(g)}$ then ${\displaystyle c\cdot f=o(g)}$, and

if ${\displaystyle f=o(F)}$ and ${\displaystyle g=o(G)}$ then ${\displaystyle f\cdot g=o(F\cdot G).}$

if ${\displaystyle f=o(F)}$ and ${\displaystyle g=o(G)}$ then ${\displaystyle f+g=o(F+G)}$

It also satisfies a transitivity relation:

if ${\displaystyle f=o(g)}$ and ${\displaystyle g=o(h)}$ then ${\displaystyle f=o(h).}$

Little-o can also be generalized to the finite case:^[2]${\displaystyle f(x)=o(g(x))\quad {\text{ as }}x\to x_{0}}$ if $${\displaystyle \lim _{x\to x_{0}}{\frac {f(x)}{g(x)}}=0.}$$ In other words, ${\displaystyle f(x)=\alpha (x)g(x)}$ for some ${\displaystyle \alpha (x)}$ with ${\displaystyle \lim _{x\to x_{0}}\alpha (x)=0}$.

This definition is especially useful in the computation of limits using Taylor series. For example:

${\displaystyle \sin x=x-{\frac {x^{3}}{3!}}+\ldots =x+o(x^{2}){\text{ as }}x\to 0}$, so ${\displaystyle \lim _{x\to 0}{\frac {\sin x}{x}}=\lim _{x\to 0}{\frac {x+o(x^{2})}{x}}=\lim _{x\to 0}1+o(x)=1}$

A relation related to little-o is the asymptotic notation ${\displaystyle \sim }$. For real valued functions ${\displaystyle f,g}$, the expression $${\displaystyle f(x)\sim g(x)\quad {\text{ as }}x\to \infty }$$ means $${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=1.}$$ One can connect this to little-o by observing that ${\displaystyle f(x)\sim g(x)}$ is also equivalent to ${\displaystyle f(x)=(1+o(1))g(x)}$. Here ${\displaystyle o(1)}$ refers to a function tending to zero as ${\displaystyle x\to \infty }$. One reads this as "${\displaystyle f(x)}$ is asymptotic to${\displaystyle g(x)}$". For nonzero functions on the same (finite or infinite) domain, ${\displaystyle \sim }$ forms an equivalence relation.

One of the most famous theorems using the notation ${\displaystyle \sim }$ is Stirling's formula$${\displaystyle n!\sim {\bigg (}{\frac {n}{e}}{\bigg )}^{n}{\sqrt {2\pi n}}\quad {\text{ as }}n\to \infty .}$$ In number theory, the famous prime number theorem states that $${\displaystyle \pi (x)\sim {\frac {x}{\log x}}\quad {\text{ as }}x\to \infty ,}$$ where ${\displaystyle \pi (x)}$ is the number of primes which are at most ${\displaystyle x}$ and ${\displaystyle \log }$ is the natural logarithm of ${\displaystyle x}$.

As with little-o, there is a version with finite limits (two-sided or one-sided) as well, for example $${\displaystyle \sin x\sim x\quad {\text{ as }}x\to 0.}$$

Further examples: $${\displaystyle x^{a}=o_{a,b}(e^{bx})\quad {\text{ as }}x\to \infty ,{\text{ for any positive constants }}a,b,}$$$${\displaystyle f(x)=g(x)+o(1)\quad \Longleftrightarrow \quad e^{f(x)}\sim e^{g(x)}\quad (x\to \infty ).}$$$${\displaystyle \sum _{n=1}^{\infty }{\frac {1}{n^{s}}}\sim {\frac {1}{s-1}}\quad (s\to 1^{+}).}$$ The last asymptotic is a basic property of the Riemann zeta function.

For eventually positive, real valued functions ${\displaystyle f,g,}$ the notation $${\displaystyle f(x)=\omega (g(x))\quad {\text{ as }}x\to \infty }$$ means $${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=\infty .}$$ In other words, ${\displaystyle g(x)=o(f(x))}$. Roughly speaking, this means that ${\displaystyle f(x)}$ grows much faster than does ${\displaystyle g(x)}$.

In 1914 G. H. Hardy and J. E. Littlewood introduced the new symbol ${\displaystyle \ \Omega ,}$^[7] which is defined as follows:

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

Thus ${\displaystyle ~f(x)=\Omega (g(x))~}$ is the negation of ${\displaystyle ~f(x)=o(g(x))~.}$

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

${\displaystyle f(x)=\Omega _{R}(g(x))\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}(g(x))\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. ^{[ 16 ]} Sin embargo, los autores que siguieron a Landau utilizan una notación diferente para las mismas definiciones: ^{[ 11 ]} 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 y se satisfacen), se utilizan actualmente en la teoría analítica de números . ^{[ 11 ] [ 12 ]}${\displaystyle \ \Omega \ ,\Omega _{+}\ ,\Omega _{-}\ ,}$${\displaystyle \ f(x)=\Omega _{\pm }(g(x))\ }$${\displaystyle \ f(x)=\Omega _{+}(g(x))\ }$${\displaystyle \ f(x)=\Omega _{-}(g(x))\ }$

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 ,~}$

donde significa que el lado izquierdo es tanto como , ${\displaystyle \Omega _{\pm }}$${\displaystyle \Omega _{+}(1)}$${\displaystyle \Omega _{-}(1)}$

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 ~.}$

Para comprender las definiciones formales, consulte la lista de símbolos lógicos utilizados en matemáticas.

The limit definitions assume ${\displaystyle g(n)>0}$ for ${\displaystyle n}$ in a neighborhood of the limit; when the limit is ${\displaystyle \infty }$, this means that ${\displaystyle g(n)>0}$ for sufficiently large ${\displaystyle n}$.

Computer science and combinatorics use the big ${\displaystyle O}$, big Theta ${\displaystyle \Theta }$, little ${\displaystyle o}$, little omega ${\displaystyle \omega }$ and Knuth's big Omega ${\displaystyle \Omega }$ notations. ^[3] Analytic number theory often uses the big ${\displaystyle O}$, small ${\displaystyle o}$, Hardy's ${\displaystyle \asymp }$, Hardy–Littlewood's big Omega ${\displaystyle \Omega }$ (with or without the +, − or ± subscripts), Vinogradov's ${\displaystyle \ll }$ and ${\displaystyle \gg }$ notations and ${\displaystyle \sim }$ notations. ^[11][4][12] The small omega ${\displaystyle \omega }$ notation is not used as often in analysis or in number theory. ^[19]

Informally, especially in computer science, the big ${\displaystyle O}$ notation often can be used somewhat differently to describe an asymptotic tight bound where using big Theta ${\displaystyle \Theta }$ notation might be more factually appropriate in a given context .^[20] For example, when considering a function ${\displaystyle T(n)=73n^{3}+22n^{2}+58}$, all of the following are generally acceptable, but tighter bounds (such as numbers 2,3 and 4 below) are usually strongly preferred over looser bounds (such as number 1 below).

1. ${\displaystyle T(n)=O(n^{100})}$
2. ${\displaystyle T(n)=O(n^{3})}$
3. ${\displaystyle T(n)=\Theta (n^{3})}$
4. ${\displaystyle T(n)\sim 73n^{3}}$ as ${\displaystyle n\to \infty }$.

While all three statements are true, progressively more information is contained in each. In some fields, however, the big O notation (number 2 in the lists above) would be used more commonly than the big Theta notation (items numbered 3 in the lists above). For example, if ${\displaystyle T(n)}$ represents the running time of a newly developed algorithm for input size ${\displaystyle n}$, the inventors and users of the algorithm might be more inclined to put an upper bound on how long it will take to run without making an explicit statement about the lower bound or asymptotic behavior.

Otra notación que a veces se usa en ciencias de la computación es (léase soft-O ), que oculta los factores polilogarítmicos. Hay dos definiciones en uso: algunos autores usan como abreviatura de para algún , mientras que otros la usan como abreviatura de . ^{[ 21 ]} Cuando es polinomial en , no hay diferencia; sin embargo, la segunda definición permite decir, por ejemplo, que mientras que la primera definición permite para cualquier constante . Algunos autores escriben O ^* con el mismo propósito que la segunda definición. ^{[ 22 ]} Esencialmente, es una versión menos precisa de la notación O grande, que ignora los factores logarítmicos en la tasa de crecimiento de la función. Dado que para cualquier constante y cualquier , los factores logarítmicos son mucho menos significativos que las potencias de e incluso más insignificantes en comparación con las exponenciales. ${\displaystyle {\tilde {O}}}$${\displaystyle f(n)={\tilde {O}}(g(n))}$${\displaystyle f(n)=O(g(n)\log ^{k}n)}$${\displaystyle k}$${\displaystyle f(n)=O(g(n)\log ^{k}g(n))}$${\displaystyle g(n)}$${\displaystyle n}$${\displaystyle n2^{n}={\tilde {O}}(2^{n})}$${\displaystyle \log ^{k}n={\tilde {O}}(1)}$${\displaystyle k}$${\displaystyle \log ^{k}n=o(n^{\varepsilon })}$${\displaystyle k}$${\displaystyle \varepsilon >0}$${\displaystyle n}$

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 \log n}$

La generalización a funciones que toman valores en cualquier espacio vectorial normado es directa (reemplazando los valores absolutos por normas), donde y no necesitan tomar sus valores en el mismo espacio. También es posible una generalización a funciones que toman valores en cualquier grupo topológico . El "proceso límite" también puede generalizarse introduciendo una base de filtro arbitraria , es decir, a redes dirigidas y . La notación puede usarse para definir derivadas y diferenciabilidad en espacios bastante generales, y también la equivalencia (asintótica) de funciones, ${\displaystyle f}$${\displaystyle g}$${\displaystyle g}$${\displaystyle x\to x_{0}}$${\displaystyle f}$${\displaystyle g}$${\displaystyle o}$

${\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 " es " de arriba. (Se reduce a si y son funciones reales positivas). Por ejemplo, es, pero . ${\displaystyle f}$${\displaystyle \Theta (g)}$${\displaystyle \lim f/g=1}$${\displaystyle f}$${\displaystyle g}$${\displaystyle 2x=\Theta (x)}$${\displaystyle 2x-x\neq o(x)}$

En 1870, Paul du Bois-Reymond ^{[ 9 ]} definió y para significar, respectivamente, Estas no fueron ampliamente adoptadas y no se usan hoy en día. La primera y la tercera son simétricas: significa lo mismo que . Landau adoptó más tarde con la definición más estricta de que el límite de es igual a 1. ${\displaystyle f(x)\succ \phi (x)}$${\displaystyle f(x)\sim \phi (x)}$${\displaystyle f(x)\prec \phi (x)}$$${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{\phi (x)}}=\infty ,\quad \lim _{x\to \infty }{\frac {f(x)}{\phi (x)}}>0,\quad \lim _{x\to \infty }{\frac {f(x)}{\phi (x)}}=0.}$$${\displaystyle f(x)\prec \phi (x)}$${\displaystyle \phi (x)\succ f(x)}$${\displaystyle \sim }$${\displaystyle f(x)/\phi (x)}$

The symbol O was first introduced by the number theorist Paul Bachmann in 1894, in the second volume of his book Analytische Zahlentheorie ("analytic number theory").^[1] The number theorist Edmund Landau adopted it, and was thus inspired to introduce in 1909 the notation o;^[2] hence both are now called Landau symbols. These notations were used in applied mathematics during the 1950s for asymptotic analysis.^[23] The symbol ${\displaystyle \Omega }$ (in the sense "is not little o of") was introduced in 1914 by Hardy and Littlewood.^[7] Hardy and Littlewood also introduced in 1916 the left and right ${\displaystyle \Omega }$ symbols ${\displaystyle \Omega _{R}}$, ${\displaystyle \Omega _{L}}$ (now commonly denoted ${\displaystyle \Omega _{+},\Omega _{-}}$).^[15] This ${\displaystyle \Omega }$ notation has been commonly used in number theory since the 1950s.^[13]

Hardy introduced the symbols ${\displaystyle \preccurlyeq }$ and advocated for Bois-Reymond's ${\displaystyle \prec }$ (as well as the already mentioned other symbols) in his 1910 tract "Orders of Infinity",^[5] but made use of them only in three papers (1910–1913). In his nearly 400 remaining papers and books he consistently used the Landau symbols O and o.^[24] Hardy's symbols ${\displaystyle \preccurlyeq }$ and ${\displaystyle \mathbin {\,\asymp \;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-} }$ are not used any more.

The symbol ${\displaystyle \sim }$, although it had been used before with different meanings,^[9] was given its modern definition by Landau in 1909^[2] and by Hardy in 1910.^[5] On the same page, Hardy defined the symbol ${\displaystyle \asymp }$, where ${\displaystyle f(x)\asymp g(x)}$ means that both ${\displaystyle f(x)=O(g(x))}$ and ${\displaystyle g(x)=O(f(x))}$ are satisfied. The notation is still used in analytic number theory.^[25][12] Hardy also proposed the symbol ${\displaystyle \mathbin {\,\asymp \;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-} }$, where ${\displaystyle f\mathbin {\,\asymp \;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-} g}$ means that ${\displaystyle f\sim Kg}$ for some constant ${\displaystyle K\not =0}$ (this corresponds to Bois-Reymond's notation ${\displaystyle f\sim g}$).