Proving Big O(1)

Question

How do I determine if the below is true or false? \begin{equation} 17^{100} + \frac{1}{n} = O(1)? \end{equation} I have tried using the c and No method but still can not come up with a solution.

Answer 1

Recall the definition of $O()$: We say that $f(n)$ is $O(g(n))$ if there are constants $c$ and $n_0$ so that $$f(n) < c\cdot g(n)\text{ whenever } n > n_0.$$ The way to think about this is to think about $c$ first and try to find some $c$ so that $f(n)$ is "eventually" bigger than $c\cdot g(n)$. Or put another way, we want to find $c$ so that $f(n) $ is bigger than $c\cdot g(n)$ when $n$ is very big. If we can do this, all we have to do is explain what we mean by "$n$ is very big", and that's what $n_0$ is for: we give $n_0$ and say that any $n$ bigger than $n_0$ is big enough.

Here we want to know if $17^{100}+\frac1n$ is $O(1)$, so we want to know if there is a constant $c$ so that $$17^{100}+\frac1n < c\cdot 1\text{ whenever $n$ is big enough.}$$

But it's easy to find such a $c$: take $c = 17^{100}+1.$

Then we get $$17^{100}+\frac1n < 17^{100}+1\text{ whenever $n$ is big enough.}$$

This is certainly true whenever $n$ is bigger than 1. So here "big enough" means "bigger than 1", and we take $n_0 = 1$, and we are done: $17^{100}+\frac1n$ is $O(1)$ because we can present $c=17^{100}+1$ and $n_0 = 1$ such that

$$17^{100}+\frac1n < \left(17^{100}+1\right)\cdot 1\text{ whenever }n>1$$

and that is the definition.