How to solve basic asymptotic algorithm problem

Question

\begin{equation} f(n) = n-100\\ g(n) = n-200 \end{equation} How can I prove that $f(n) = O(g(n))$ or $f(n) = Ω(g(n))$?

Answer 1

Well, the first thing I notice as I look at this situation is that $f(n)$ and $g(n)$ are negative initially. We're going to want them to be positive, at least, for otherwise, $C\cdot g(n)<f(n)$ for any positive $C.$ Thus, we only need to consider $n>200.$

Now, in the comments, you pointed out that you'd gotten from $$n-100\le C\cdot(n-200)$$ to the statement $$n\cdot(C-1)-100(C-2)\ge 0.$$ Unfortunately, something appears to have gone wrong. Let me take you through the steps. $$n-100\le C\cdot(n-200)\\n-100\le Cn-200C\\-100\le Cn-n-200C\\-100\le n\cdot(C-1)-200 C\\0\le n\cdot(C-1)+100-200 C\\0\le n\cdot(C-1)+100(1-2C).$$

At this point, you're basically there! Let's rewrite it instead as $$n\cdot(C-1)\ge100\cdot(2C-1),$$ and observe that $C\le 1$ absolutely won't get the job done, so we can assume $C>1,$ meaning $C-1>0.$ Thus, we get the equivalent inequality $$n\ge100\cdot\frac{2C-1}{C-1}=100\cdot\left(\frac{2C-2}{C-1}+\frac1{C-1}\right)=200+\frac{100}{C-1}$$ Does that get you there?