1
$\begingroup$

Is this true, that:

$$ g(x) = f(x) + O(x) \rightarrow f(x) = g(x) + O(x)$$

In other words, is the order relation symmetric? How can I prove this?

I think this is true, since:

$$ g(x) = f(x) + O(x) \rightarrow g(x) - f(x) = O(x) $$

So in other words:

$$ \frac{|g(x) - f(x)|}{x} = K $$

For some value $K$ as $x \rightarrow \infty$. Similarly, we see that:

$$ f(x) = g(x) + O(x) \rightarrow f(x) - g(x) = O(x) $$

So in other words:

$$ \frac{|f(x) - g(x)|}{x} = M $$

For some other value $M$ as $x \rightarrow \infty$. But since $|g(x) - f(x)|$ = $|f(x) - g(x)|$, we have that $K = M$. So the relation holds.


Is this the way to prove this?

$\endgroup$

1 Answer 1

0
$\begingroup$

The idea is correct, but the problem with these proofs is that what we write as $O(x) $ is actually just some element from the set $O(x)$. So the most rigorous way would probably be to pick a representative element. Something like: let $ h\in O(x) $ such that $f(x) =g(x) +h(x) $ then $g(x) =f(x) - h(x) $ and since $-h \in O(x) $ our hypotesis holds. If you find it tricky, try to find the rigorous definition of $O(f)$.

$\endgroup$
4
  • $\begingroup$ So the statement is correct then, right? The proof just needs a bit more rigor? I find this Big-O stuff to sort of be 'incomplete' in a way. I sometimes want to know the direction of my error, and so, I just need to resort to standard error analysis right? ie Big-O can't tell you the direction of your error. $\endgroup$ Oct 30, 2019 at 11:53
  • $\begingroup$ Exactly, Big-O notation isn't something one would use for error analysis. It just tells you how a function "behaves near infinity". In fact sometimes you could say f(x) = O(g(x)), but for certain values of x the error would be huge. Thats why in algorithm analysis one usually needs to take more factors into consideration. $\endgroup$
    – Boxonix
    Oct 30, 2019 at 12:25
  • $\begingroup$ And yes O(x) = O(-x) $\endgroup$
    – Boxonix
    Oct 30, 2019 at 12:26
  • $\begingroup$ Thanks for your help! $\endgroup$ Oct 30, 2019 at 14:44

You must log in to answer this question.

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