Prove that $n^2\in \mathcal O(n^2-1)$.

Question

Prove that $$\smash { n^2\in\mathcal{O}(n^2 -1)}$$

---

I don't quite understand what strategy I should use when trying to prove the following big $\mathcal{O}$ notation that doesn't include the use of limits. Whenever I try to find a $C$ when $n>=2$, I can never get it to be a positive real. Any advice would be appreciated.

Answer 1

$ g(x) \in \mathcal{O}(f(x))$ means that there exists a constant $C$ so that $$ |g(x)| \leq C |f(x)| $$

In our case, notice that if $C=3$ for example, the inequality will be true

$$ n^2 < C |n^2-1| $$

for $n > n_0$ for instance $n_0$ can be $2$ or $3$,...

$C$ can be $2$ also, or $1.5$, but $C=1$ wont work.

Answer 2

There is an implied limit in the big-O notation; it only makes sense "as $n\to$ something". In this case? $n$ is traditionally a name for an integer variable, and that something would be $\infty$.

If we used a different limit, we might get a different result. As $n\to 0$, $n^2$ is a smaller order than $n^2-1$; $\lim_{n\to 0}\frac{n^2}{n^2-1}=0$ and we could upgrade the $O$ to a $o$. As $n\to 1$, $n^2\to 1$ is bigger than $n^2-1\to 0$, and in that case we have $n^2\not\in O(n^2-1)$.

Answer 3

For any $n\ge 2$, you want $$ n^2\le C(n^2-1) $$ which rerarranges to $$ C\ge \frac{n^2}{n^2-1}=1+\frac1{n^2-1} $$ Since $n\ge 2$, we have $1+\frac1{n^2-1}\le \frac43.$ Therefore, for any $C\ge \frac43$, you have $n^2\le C(n^2-1)$ for all $n\ge 2$. This proves $n^2\in \mathcal O(n^2-1)$.