1
$\begingroup$

I have this question as an assignment in my Java Algorithms class, and i'm aware that d(n)+e(n) is the same as O(f(n)+g(n)). I dont know why the same doesnt apply to subtracting. Can someone help me? I'm lost..

$\endgroup$
0
1
$\begingroup$

Let $d(n) = 2n$ and $e(n) = n$. Then $$d(n)-e(n) = n.$$ Since $d(n) = O(n)$ and $e(n) = O(n)$, we have that $$f(n) = g(n) = n,$$ so $$O(f(n)-g(n)) = O(n-n) = O(1),$$ and clearly $$n \neq O(1).$$

$\endgroup$
1
  • $\begingroup$ Thank you for the answer, but unfortunately the question is a duplicate. Please check the answer over there; if you think yours adds something worth keeping, please repost your answer over there. Thanks! $\endgroup$
    – Raphael
    Feb 1 '16 at 23:29

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