Is it true that $|O(2n) - O(n)|=O(n)$?

72 Views Asked by At

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?

2

There are 2 best solutions below

2
On BEST ANSWER

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

0
On

I think it is correct: $$ \left| \frac{O(2n)-O(n)}{n} \right| = \left| O(1)-O(1) \right| = O(1). $$