Resta de Big $O$ ' s

Question

Así que nos pidieron para probar algo en clase, pero no puedo entender la siguiente expresión:

¿Qué es $O(n^2)-O(n^2)$?

Entiendo la notación grande de O, pero lo que no entiendo es la resta de dos grandes $O$'s. mi primer pensamiento fue que los conjuntos son infinitos pero todavía idéntico por lo que la resta será un conjunto vacío.

Por favor arrojar algo de luz...

Answer 1

Si $O(n^2)-O(n^2)$ se define como el conjunto de secuencias $(z_n)$ tal que existe $(x_n)$ y $(y_n)$ $x_n\in O(n^2)$, $y_n\in O(n^2)$ y, para todos los $k$, $z_k=x_k-y_k$, entonces el $O(n^2)-O(n^2)=O(n^2)$, como se ve fácilmente probando la doble inclusión.

Más generalmente, para cada % de secuencias $(x_n)$y $(y_n)$, $O(x_n)-O(y_n)=O(z_n)$ $z_n=|x_n|+|y_n|$ o, equivalente, $z_n=\max{|x_n|,|y_n|}$.