I need to prove or contradict:$$|O(2n) - O(n)|=O(n)$$ I try: $$\\f(n)=1.5n\in O(2n),g(n)=0.25n\in O(n),h(n)>0\in O(n) : \\ |1.5n - 0.25n|=h(n)\\1.h(n)=1.25n \in O(n)\\ but: 2. h(n)=-1.25n \notin O(n)$$ Is that true?
Asked
Active
Viewed 71 times
2 Answers
2
Your conclusion is wrong. $-1.25 n$ is in $O(n)$. Re-check your definition of $O(n)$. It contains absolute values.
Also, it is fairly easy to show that $O(n) = O(2n)$.
5xum
- 123,496
- 6
- 128
- 204
-
ok,thanks..so how can I prove that? – user2976686 Apr 01 '14 at 09:47
-
Using the definition of $O(n)$ take any function in $O(n)$ and show that it is in $O(2n)$. Then take any function in $O(2n)$ and show that it is in $O(n)$ – 5xum Apr 01 '14 at 09:48
1
I think it is correct: $$ \left| \frac{O(2n)-O(n)}{n} \right| = \left| O(1)-O(1) \right| = O(1). $$
Siminore
- 35,136