Big Oh notation of $100n + 1$

Question

I am trying to find the Big Oh notation of $100n + 1$. I know that $f(n) \le c \cdot g(n)$ $\forall n \ge k \implies f(n) \in O(g(n))$. How do I choose the best $c$ and $k$? My assumption would be to choose $c = 101$ and $k = 1$, but I am not sure if that is correct.

Thank you for your help!

Answer 1

There is no common sense of comparing such pairs other than whether pair is suitable. Possible general algorithm for choosing suitable pair $(c, k)$ is the following:

• Select arbitrary positive integer $k$.
• Compute $c = \sup_{n \ge k} \frac{f(n)}{g(n)}$.
• If such $c$ doesn't exist (because of division by zero), select other (greater) $k$ and return to the previous step.
• If $c$ is infinity, then $f(\cdot) \notin O(g(\cdot))$.
• Pair $(c, k)$ is suitable. If you don't like it for some reason start this process from scratch.

(Also it is possible to select any $c \ge \sup_{n \ge k} \frac{f(n)}{g(n)}$, equality is not really needed here.)

If you have some criterium of comparing which of two suitable pairs is better, then you will need to modify this algorithm appropriately. As it is writtern in comments pair $(c, k) = (101, 1)$ is suitable for proving that $100n + 1 \in O(n)$. However one could think that pair $(c, k) = (100\frac{55}{89}, 2)$ is better than $(101, 1)$ in this case for some reason. And it is his/her right because both pairs are suitable.