-1
$\begingroup$

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)$?

$\endgroup$
  • $\begingroup$ 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)$?) $\endgroup$ – user53923 Apr 7 '17 at 14:51
  • $\begingroup$ See also cs.stackexchange.com/a/30599/65870 under Pitfalls of convention $\endgroup$ – user53923 Apr 7 '17 at 14:54
  • $\begingroup$ @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. $\endgroup$ – futtetennista Apr 7 '17 at 15:16
  • $\begingroup$ 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. $\endgroup$ – Raphael Apr 7 '17 at 20:40
  • 1
    $\begingroup$ @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. $\endgroup$ – David Richerby Apr 8 '17 at 9:10
3
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.$$

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – futtetennista Apr 8 '17 at 7:34
  • $\begingroup$ @futtetennista It is not true. What you need is a counterexample. You cannot prove a wrong proposition. $\endgroup$ – hengxin Apr 8 '17 at 7:39
  • $\begingroup$ we're saying the same thing: $g(x) ≠ 0$ just showing it in different ways. $\endgroup$ – futtetennista Apr 8 '17 at 7:42
  • $\begingroup$ 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$. $\endgroup$ – David Richerby Apr 8 '17 at 9:03
-1
$\begingroup$

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)$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – futtetennista Apr 7 '17 at 13:18
  • 3
    $\begingroup$ You can't say O (n^2) = M * n^2. O (n^2) ≤ M*n^2, and - O (n^2) ≥ -M' n^2. $\endgroup$ – gnasher729 Apr 7 '17 at 20:05
  • $\begingroup$ Look at your definition of O (g(n)) and see what happens if a function is negative. $\endgroup$ – gnasher729 Apr 7 '17 at 20:07
  • $\begingroup$ @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. $\endgroup$ – futtetennista Apr 8 '17 at 7:27
  • 1
    $\begingroup$ @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. $\endgroup$ – David Richerby Apr 8 '17 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.