# Difference of Big-Oh terms — what is the result?

I'd like to double-check my understanding of Big-Oh.

The definition is that $f(n) = O(g(n))$ if $|f(x)| ≤ M\,|g(x)|$ for a natural number $M$ and for sufficiently large values of $x$.

Now, if $g(n) = O(n^2) - O(n^2)$, may we conclude that $g(n) = 0$? If not, what can we say about $g(n)$?

• Note that $O(n^2)$ is not a function, but a class of functions. (While writing $f(x) = O(n^2)$ is common, $f(x) \in O(n^2)$ would make more sense in my opinion). This makes the definition of $g(x)$ as $O(n^2) - O(n^2)$ unclear. Can you clarify what it should mean? (perhaps $g(x) = h(x) - f(x)$ where both $h(x) = O(n^2)$ and $f(x) = O(n^2)$?) – user53923 Apr 7 '17 at 14:51
• See also cs.stackexchange.com/a/30599/65870 under Pitfalls of convention – user53923 Apr 7 '17 at 14:54
• @user53923 I wish I could but that's an exercise of a book I'm reading and that's the full description of the problem. Also, thanks for the interesting link. – futtetennista Apr 7 '17 at 15:16
• 1) "Time complexity of g(x) = O(n²) − O(n²)" -- that's not a thing. 2) How does your book define "-" for Landau terms? Work from there -- unfold definitions. – Raphael Apr 7 '17 at 20:40
• @user53923 It's entirely standard to write things like $g(x) = x^2 + O(x)$ to mean $g(x)=x + h(x)$ for some function $x\in O(x)$. This is much more specific than just saying $g(x)=O(x^2)$, since $10x^2 + x^{1.999}$ is in $O(x^2)$ but is not of the form $x^2+O(x)$. So "$g(x)=O(x^2)-O(x^2)$" does indeed mean that $g(x)=h(x)-f(x)$ for some $h,f\in O(x^2)$. Allowing us to write things like $x^2+O(x)$ is exactly the reason why we abuse notation by saying $g=O(f)$, rather than $g\in O(f)$: pretending that $O(x)$ is a function lets us include it in arithmetic expressions, which is very useful. – David Richerby Apr 8 '17 at 9:10

We have $g(x) = f(x) - h(x)$ for some functions $f,h\in O(x^2)$. Since the functions are measuring the running time of some algorithm, I'll assume explicitly that $f(x)\geq 0$ and $h(x)\geq 0$, for all $x$. So there are constants $c_1$ and $c_2$ such that, for all large enough $x$, $f(x)\leq c_1x^2$ and $h(x)\leq c_2x^2$.

We have $g(x) = f(x) - h(x)$. Since $h(x)\geq 0$ for all $x$, we certainly know that $g(x)\leq f(x)$, since $g(x)$ is "$f(x)$ minus something non-negative." So, in particular, we have $g(x)\leq c_1x^2$ for all large enough $x$, i.e., $g(x) = O(x^2)$.

However, we cannot conclude anything stronger in the general case. It is possible, for example, that $f(x) = x^2$ and $h(x) = 0$ for all $x$. Then $g(x) = x^2$. So, without more information about $f$ and $h$, we can't conclude that $g$ is any smaller than $x^2$.

Let's say we are talking about runtimes of algorithms, not functions. Then we can use the definition of $O (f (n))$ the way it is given here. But where would we encounter something like $O (f (n)) - O (g (n))$?

Here's a practical situation: I have a complex algorithm. One step in that algorithm has a runtime of $O (f (n))$. I could modify that step in a way that it now takes $O (g (n))$. How much faster will my algorithm be?

We can say naively that the improvement is $O (f (n)) - O (g (n))$. If $f (n), g (n) = O (n^2)$ then we can say equally naively that the improvement is $O (n^2) - O (n^2)$. But what is the actual improvement?

The fact is that with the information given, we have no idea. f (n) could always be 100 times larger than g (n), or always 100 times smaller, or sometimes larger and sometimes smaller; that's absolutely allowed by the definition of O (). All we can say is that the runtime of the algorithm will not improve by more than $O (n^2)$, and will not get worse by more than $O (n^2)$. We can't say whether it will improve or get worse, and it might be different depending on n.

But if we talk about functions, and not algorithms, then we must use a definition of O (f (n)) that takes into account negative values and somehow works in a meaningful way for negative values.

It is OK to say $$O(n^2) - O(n^2) = O(n^2)$$ which means that subtracting a function in $O(n^2)$ from another one in $O(n^2)$ gives a function in $O(n^2)$. Note that in algorithm analysis, we often assume that the functions considered take on positive values.

Be careful, because we don't have $$\Theta(n^2) - \Theta(n^2) = \Theta(n^2).$$ In contrast, we do have $$\Theta(n^2) + \Theta(n^2) = \Theta(n^2).$$

We don't have $g(n) = O(n^2) - O(n^2) \implies g(n) = 0$. For example, $$f_1(n) = n^2 + n = O(n^2), \;f_2(n) = n = O(n^2),$$ $$f_1(n) - f_2(n) = n^2 = \Theta(n^2) \neq 0.$$

• I'm sold on that point :) I just wanted to show it by using only the given definition of Big-Oh (and some basic math) – futtetennista Apr 8 '17 at 7:34
• @futtetennista It is not true. What you need is a counterexample. You cannot prove a wrong proposition. – hengxin Apr 8 '17 at 7:39
• we're saying the same thing: $g(x) ≠ 0$ just showing it in different ways. – futtetennista Apr 8 '17 at 7:42
• A more dramatic example that $g(n)=f_1(n)-f_2(n)$ with $f_1,f_2\in O(n^2)$ doesn't imply $g(n)=0$ is to put $f_1(n)=n^2$ and $f_2(n)=0$. – David Richerby Apr 8 '17 at 9:03

My (proposed) solution is:

$g(n) = O(n^2) - O(n^2) = M*n^2 - M'*n^2 = (M-M')*n^2 = M''*n^2 = O(n^2)$

that is:

$g(n) = O(n^2)$

• I read cs.meta.stackexchange.com/questions/597/… and decided to write my question this way. Not sure it was the most appropriate way though. Feedback on the proposed solution is very welcomed. – futtetennista Apr 7 '17 at 13:18
• You can't say O (n^2) = M * n^2. O (n^2) ≤ M*n^2, and - O (n^2) ≥ -M' n^2. – gnasher729 Apr 7 '17 at 20:05
• Look at your definition of O (g(n)) and see what happens if a function is negative. – gnasher729 Apr 7 '17 at 20:07
• @gnasher729 you caught another error in the way I formulated the question, specifically in the definition of Big-Oh. Functions do some work (that is they use time resources) and for that reason their output can never be negative in the cases I consider. – futtetennista Apr 8 '17 at 7:27
• @futtetennista No, functions don't do work. When you write $h(x)=O(x)$, $h$ is a mathematical function, not a programming language function. It is just a map from numbers to numbers. You're using a function to represent the running time of some algorithm. Because the algorithm does some work, the function measuring its running time cannot be negative. – David Richerby Apr 8 '17 at 9:16