So we were asked to prove something in class, but I can't understand the following expression:
What is $O(n^2)-O(n^2)$?
I understand big O notation, but what I don't understand is the subtraction of two big $O$'s. my first thought was that the sets are infinite but yet identical so the subtraction will be an empty set.
Please shed some light...
If $O(n^2)-O(n^2)$ is defined as the set of sequences $(z_n)$ such that there exists $(x_n)$ and $(y_n)$ with $x_n\in O(n^2)$, $y_n\in O(n^2)$, and, for all $k$, $z_k=x_k-y_k$, then $O(n^2)-O(n^2)=O(n^2)$, as readily seen by proving the double inclusion.
More generally, for every sequences $(x_n)$ and $(y_n)$, $O(x_n)-O(y_n)=O(z_n)$ with $z_n=|x_n|+|y_n|$ or, equivalently, with $z_n=\max\{|x_n|,|y_n|\}$.