[Solved]: Show that if d(n) is O( f (n)) and e(n) is O(g(n)), then d(n)−e(n) is not necessarily O( f (n)−g(n))

Problem Detail: 

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

Asked By : Kajamaz

Answered By : gardenhead

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52574