A Big-O Drill

An easy warm up

To prove this, we want to find positive constants $c'$ and $n'$ for which

$$0 \leq n \leq c' n \qquad \text{ for all }n \geq n'$$

One way to approach a problem

Suppose we want to show that $n^2+2n+100$ is $O(n^2)$.

Demonstration: To do this, we begin by showing an upper bound on each term of the form $c \times n^2$, for some constant $c$.

For $n \geq 1$,

$$\begin{align*} n^2 &\leq 1n^2\\ 2n &\leq 2 n^2\\ 100 &\leq 100 n^2 \end{align*}$$ ...