Say we have a variable $n > 0$ and a constant $d \geq 0$. Is is then true that $O(n-d) = O(n)$?
Asked
Active
Viewed 28 times
0
-
2Start by writing down the definitions of both left and right sides. It should be obvious from there. – Alex R. Mar 31 '20 at 21:11
-
Ahh good idea :) So it is a correct derivation that since $n-d \leq c \cdot n$ for some $c \geq 1$, it is true that $O(n-d) = O(n)$? If so, sorry for wasting your time :) – That Guy Mar 31 '20 at 21:13
-
In essence yes, but technically you need to prove both directions, i.e. $n-d\leq c_1 n$ and $n\leq c_2(n-d)$ for some constants $c_1,c_2$ and $n$ large enough. The reason you need both directions is in an example like $O(n)?=?O(n^2)$, in which case $n\leq cn^2$ but, clearly this won't hold with $\geq$. – Alex R. Mar 31 '20 at 21:15
-
But isn't the need for both directions only for showing $\theta(f(n))$, i.e. both upper and lower bound? – That Guy Mar 31 '20 at 21:19
-
Look at the counterexample in my last comment. $n\leq cn^2$ but $n^2\leq dn$ won't hold for any $d$. In other words $n=O(n^2)$ but $n^2\neq O(n)$. – Alex R. Mar 31 '20 at 21:21
-
Yes I see your counter example but why would I wish to show it with $\geq$ when I only want to show that some function $O(n-d)$ is upper bounded? – That Guy Mar 31 '20 at 21:23
-
@AlexR. that was the final question :))) – That Guy Mar 31 '20 at 21:41