La aritmética de las reglas de la notación big O, poco o notación y así sucesivamente...

Question

Hay muchas notaciones asintóticas como el big O notación: notación Omega, poco o notación, ... por Lo tanto hay muchas reglas de la aritmética para ellos. Por ejemplo, Donald Knuth estados en Concreto Mathemtics (p. 436) las siguientes reglas (sin prueba):

• $f(n)=O(f(n))$
• $c O(f(n)) = O(f(n))$ si $c$ es constante
• $O(O(f(n))) = O(f(n))$
• ...

Mi Pregunta: ¿Puede recomendar una referencia en el que todas las reglas de la aritmética de las notaciones asintóticas se afirmó y demostró? Sería genial si también las conexiones entre las notaciones asintóticas se formulan y se muestra, por ejemplo,$O(o(f(n))=o(f(n))$.

A mi los resultados de la investigación hasta el momento:

• A la pregunta ¿cuáles son las reglas para los iguales signos con los grandes-O y poco-o? investiga las reglas de interpretación de las notaciones asintóticas.
• El artículo de la Wikipedia "Big O"notación de los estados algunas reglas, pero sin una prueba.
• (Como ya se ha mencionado) hay algunas reglas en Concreto de las Matemáticas página 436 sin pruebas.
• El artículo "Algunas Reglas para Big-Oh Notación de" listas de algunas reglas (sin prueba).

Razón de mi pregunta: puedo escribir mi tesis de que mucho bases sobre las notaciones asintóticas. Yo quiero probar toda la aritmética de reglas que utilizan, que son un montón... (yo también uso otras notaciones como el gran Delta de notación). Una lista de los ya demostró aritmética reglas - que puedo citar - sería genial aquí ;-)

Actualización: he tenido una idea para minimizar el número de reglas de la aritmética a través de la generalización del concepto de notaciones asintóticas. Describo esta idea en el MO hilo Generalización de notaciones asintóticas como big O, o poco o notación.

Answer 1

Una hermosa presentación puede encontrarse en N. G. De Bruijn clásico: Asintótica de los Métodos de Análisis. Usted encontrará aritmética de las reglas de la Bachmann-Landau símbolos en la sección de Introducción.

Otro clásico es Asymptotics y Funciones Especiales de F. W. J. Olver. El primer capítulo, Introducción al Análisis Asintótico también proporciona una completa introducción de $\sim, \mathcal{o}$ $\mathcal{O}$ notación.

Para una discusión histórica recomiendo el papel de Gran Omicron y Grandes Omega y Grandes Theta por D. E. Knuth.

Answer 2

Yo tenía una idea de cómo acortar la lista de reglas de la aritmética. Gracias a un comentario de Douglas Zare la lista de las necesarias reglas de la aritmética se hizo aún más corto.

La idea: Nota, que $O(\cdot)$ está completamente descrito por conocer a $O(1)$ porque $$(\epsilon_n)_{n\in\mathbb N} \in O(a_n) \iff \left(\left|\frac{\epsilon_n}{a_n}\right|\right)_{n\in \mathbb N} \in O(1)$$ This circumstance can be condensed in the relation $a_ n O(1) = O(a_n)$. The above equivalence and characteristic equation $a_n Un(1) = A(a_n)$ hold for other asymptotic notations too, i.e for all $\in\{s,\omega \Theta, S\}$ (whereby $(\epsilon_n)_{n\in\mathbb N} \S(a_n)$ shall be the notation for $\epsilon_n \sim a_n$) [1].

Porque notaciones asintóticas $A(\cdot)$ están completamente definidas por el conocimiento de $A(1)$ la lista de necesarios aritmética de las reglas se vuelven más cortos. Para $A,B,C\in\{o,\omega, \Theta, S\}$ nos encontramos con:

1. $(1)_{n\in\mathbb N} \in A(1) \implies (a_n)_{n\in\mathbb N} \in A(a_n)$
2. $A(1) \subseteq B(1) \implies A(a_n) \subseteq B(a_n)$
3. $A(1)\cdot B(1) \subseteq C(1) \implies A(a_n)\cdot B(b_n) \subseteq C(a_n\cdot b_n)$
4. $A(1)\cdot B(1) \subseteq C(1) \implies A(B(a_n)) \subseteq C(a_n)$
5. $A(1)+ B(1) \subseteq C(1) \implies A(a_n) + B(a_n) \subseteq C(a_n)$

Estas reglas son fáciles de probar, cuando la propiedad $a_n A(1) = A(a_n)$ es utilizado. Por ejemplo, bajo la premisa de $A(1)+ B(1) \subseteq C(1)$ tenemos

$$A(a_n) + B(a_n) = a_n (A(1)+B(1)) \subseteq a_n C(1) = C(a_n)$$

La media aritmética de las reglas para los conjuntos de la forma $A(1)$ a menudo son fáciles de ver. Por ejemplo, $O(1)\cdot o(1) \subseteq o(1)$ es la conocida proposición

$$\limsup_{n\to\infty} a_n < \infty \land \lim_{n\to\infty} b_n = 0 \implies \lim_{n\to\infty} a_n b_n = 0$$

Así, a partir de la regla 4 siga $O(a_n) \cdot o(b_n) \subseteq o(a_n \cdot b_n)$) y de la regla 3 de la siguiente manera $O(o(a_n)) \subseteq o(a_n)$.

Conclusión: Muchos aritmética de las reglas siguen directamente de la media aritmética de las reglas para los conjuntos de la forma $A(1)$ a través de la relación $a_n A(1) = A(a_n)$. Las reglas para los conjuntos de $A(1)$ a menudo son bien conocidos propuestas de análisis real de las secuencias. Ver también Cuáles son las características y propiedades de notaciones asintóticas?

Answer 3

El único resultado sea necesario para probar su primera declaración es que $\infty > 1 > 0$.

El único resultado sea necesario demostrar que el otro declaraciones es que, si $\infty > a > 0$ y $\infty > b > 0$, entonces $\infty > ab > 0$.