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 Answers
$\begingroup$
$\endgroup$
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)$.
-
-
$\begingroup$ 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)$ $\endgroup$– 5xumApr 1, 2014 at 9:48
$\begingroup$
$\endgroup$
I think it is correct: $$ \left| \frac{O(2n)-O(n)}{n} \right| = \left| O(1)-O(1) \right| = O(1). $$