Notación O grande anidada

Digamos que tengo un gráficocon aristas. Quiero ejecutar BFS en que tiene un tiempo de ejecución de .$|G|$$|E|=O(V^2)$$G$$O(V+E)$

Se siente natural escribir que el tiempo de ejecución en este gráfico sería y luego simplificar a .$O(O(V^2)+V)$$O(V^2)$

¿Hay alguna dificultad para usar un atajo de "quitar-el-anidado-O" (no solo en este caso, sino en general)?

Permítanme comenzar con una recomendación: trate la notación de Landau tal como debería (debería) tratar el redondeo: ronda raramente, ronda tarde. Si sabes algo más preciso que , Úsalo hasta que hayas terminado con todos los cálculos y Landauify al final.$O(.)$

---

En cuanto a la pregunta, profundicemos en este abuso de notación¹. ¿Cómo interpretaríamos algo como ? Deberíamos reemplazar con su definición de adentro hacia afuera. Entonces, obtenemos$h \in O(f + O(g))$$O$

$\qquad \displaystyle \exists g' \in O(g).\, h \in O(f + g')$

y entonces

$\qquad \displaystyle \exists g' \in O(g).\,\exists d>0.\, \forall n.\, h(n) \leq d(f(n) + g'(n))$

que es equivalente a

$\qquad \displaystyle \exists c > 0.\,\exists d>0.\, \forall n.\, h(n) \leq d(f(n) + cg(n))$.

Como ciertamente² $d(f(n) + cg(n)) \leq cd(f(n) + g(n))$, vemos que esto es equivalente a $h \in O(f + g)$; la pérdida de precisión es ignorada por$O$ de todas formas.

---

¿Qué pasa con otras combinaciones, digamos $h \in O(f + \Omega(g))$? Si intentamos lo mismo aquí, obtenemos

$\qquad \displaystyle \exists g' \in \Omega(g).\, h \in O(f + g')$.

Pero esta es una tautología: $h$ciertamente está limitado por algo arbitrariamente grande. Por lo tanto, combinar los límites superior e inferior de esta manera no tiene sentido.

---

1. $O(.)$y los otros símbolos de Landau asignan funciones a clases de función. Alimentarlo con una clase de función no tiene significado inmediato.
2. Al menos si consideramos solo funciones positivas, que podemos asumir con seguridad cuando hablamos de tiempos de ejecución. No estoy seguro de que esto funcione en general.

Solo quería agregar esto porque recientemente lo encontré. Si bien este atajo está bien con la suma y la multiplicación (cuando no se mezcla$O$ con $\Omega$; ver la respuesta aceptada), se debe tener cuidado al usar exponentes. Por ejemplo:

$$O(n^{O(m)}) \not= O(n^m).$$ En este ejemplo, $n^{2m}$ pertenece a la primera clase pero no a la segunda.

Por definición, $O(g)$ es un conjunto y si usa esta notación anidada, tendría un conjunto en un conjunto, lo que sería incorrecto.

La definición de la notación O

$O(g) = \left \lbrace f|\exists c > 0\exists x_0>0 \forall x > x_0: |f(x)| \leq c *|g(x)|\right \rbrace$

El error

Usaste términos como $O(O(n)+k)$ donde k y n son funciones y $O(n)$es un conjunto. Pero, ¿cuál es el resultado de una función agregada a un conjunto? ¡No está definido!

Versión correcta

En lugar de utilizar los símbolos de Landau anidados, puede hacer lo siguiente: $O(m+k),m \in O(n)$

En la sección 9.3 "$O$Manipulación "del libro Matemáticas concretas (segunda edición), Knuth ha enumerado algunas reglas de manipulación en el$O$-notation (En lo siguiente, supongo que ambos $f(n)$ y $g(n)$son positivos observe que se ha cambiado el orden de las reglas).

$$\begin{gather} (1). \quad n^m = O(n^{m'}), \quad m \le m' \\ (3). \quad f(n) = O(f(n)) \\ (5). \quad O(O(f(n))) = O(f(n)) \\ (4). \quad c \cdot O(f(n)) = O(f(n)) \\ (2). \quad O(f(n)) + O(g(n)) = O(f(n) + g(n)) \\ (6). \quad O(f(n)) O(g(n)) = O(f(n) g(n)) = f(n) O(g(n))\\ \end{gather}$$

Por (3), puede envolver / desenvolver una función $f(n)$con una notación O. Luego, mediante (5), puede envolver / desenvolver (o llamar, anidar ) veces arbitrariamente finitas. Usando (4), también puede agregar / eliminar factores de multiplicación constantes a / de$O$.

Luego, (2) y (6) le permiten manipular anidados $O$-notaciones en la forma compatible con $+$ y $\times$.