0

I'm not sure if what I'm asking even makes sense but it's a property of big-O that if $T_1(n) = O(f(n))$ and $T_2(n) = O(g(n))$, then

$T_1(n) + T_2(n) = O(f(n) + g(n))$, or less formally its $O(max(f(n), g(n)))$. And also $T_1(N) * T_2(n) = O(f(n) * (g(n))$.

Do similar properties exist for the inverse of these two operations. I've been told without explanation that $T_1(n) - T_2(n) = O(f(n) + g(n))$. Why is that so? Is it because time would need to be spent computing each value before the operation could be performed?

user1070725
  • 1
  • The first property holds only when $f$ and $g$ are assumed positive. For differences, consider the following example. As $x \to 0$, we have $x = O(x)$ and $2x = O(x)$. But $2x - x \ne O(x-x) = 0$. For quotients, say $f_1 = O(g_1)$ and $f_2 = O(g_2)$. You can't conclude from this that $f_1/f_2 = O(g_1/g_2)$. The reason is that the hypothesis says $f_1$ and $f_2$ aren't too big. But knowing $f_2$ isn't too big doesn't help you to say that $f_1/f_2$ isn't too big. In fact, the smaller $f_2$ is, the larger $f_1/f_2$ is. – David Jan 11 '16 at 06:59
  • @David Technically, $0$ is still $\mathcal O(x)$. So $f-g = \mathcal O(\max(f,g))$ is correct – Kitegi Jan 11 '16 at 10:39
  • @Farnight. My point is that what the OP said for $+$ and $\cdot$ doesn't apply to $-$ and $/$. $x \ne O(0)$. – David Jan 11 '16 at 17:16
  • @David Oh yea, I didn't see the part where he wrote $\mathcal O(f(x)+g(x))$ – Kitegi Jan 11 '16 at 18:00

1 Answers1

0

That is true, because when we say a sequence $T(n) = O(f(n))$, where $f(n)$ is asymptotically positive, we mean that there exists $a > 0$, $N > 0$ so that for all $n > N$ \begin{align*} |T(n)| \leq af(n) \end{align*} You can check against this defining property for $T_1(n)-T_2(n)$

Shengjia Zhao
  • 611