2
$\begingroup$

When trying to assess the Big $O$ of two functions that are added together, we take the max of the two. What happens if there is subtraction instead of addiiton?

for instance: $$f(n) = O(n^3) $$ $$ \text{and} $$ $$g(n) = O(n^3)$$ then $$ (f-g)(n)$$

$\endgroup$
5
  • $\begingroup$ You want to know if $(f-g)(n)$ is $O(n^3)$ ? $\endgroup$
    – brick
    Commented Nov 20, 2014 at 19:13
  • $\begingroup$ basically yes, do I still take the max which in this case, they are the same $\endgroup$ Commented Nov 20, 2014 at 19:14
  • $\begingroup$ If you consider the max of the two it won't be wrong (still $f-g$ will be the same as it). However if you know what exactly are these functions it's better to substract them and bound the result. You'll get something way more accurate. $\endgroup$
    – brick
    Commented Nov 20, 2014 at 19:21
  • $\begingroup$ What if $f(n) = bigO(n^2)$, would you still take the max of the two, or the min? $\endgroup$ Commented Nov 20, 2014 at 19:23
  • $\begingroup$ It's the max. If $f(n) = n^2$ and $g(n) = n^3$, then $(f - g)(n) = n^2 - n^3$. However $|n^2 - n^3| \leq |n^3|$ for all sufficiently large $n$, so $(f - g)(n) = O(n^3)$. Note that $(f-g)(n) \neq O(n^2)$. $\endgroup$
    – brick
    Commented Nov 20, 2014 at 19:31

1 Answer 1

5
$\begingroup$

Note that the sign of a function doesn't matter in $O $-notation:

If $f(n)\in O (h(n)) $ then $-f(n)\in O (h(n))$ follows directly from the definition of the $O $-Notation.

For two functions $f (n)\in O (h_1 (n)) $ and $g (n)\in O (h_2 (n))$ you know $$f(n)+g (n)\in O (\max (h_1 (n), h_2 (n))). $$ where in this case $\max (h_1 (n), h_2 (n))=h_1(n)$ means that $h_2 (n)\in O ( h_1 (n))$ respectively $\max (h_1 (n), h_2 (n))=h_2(n)$ means that $h_1 (n)\in O ( h_2 (n))$ .

Therefore, you can follow $$f (n)-g (n)=f (n)+ (-g (n))\in O (\max (h_1 (n), h_2 (n)))$$ since $-g (n)\in O (h_2 (n))$, too.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .