2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What do you mean "that doesn't include the use of limits"? Big $O$ is defined via limits. $\endgroup$ – lulu Mar 2 at 20:47
  • $\begingroup$ using the definition of a limit. I want to try to solve it just using inequalities. $\endgroup$ – neet Mar 2 at 21:08
  • $\begingroup$ You can not avoid the notion of a limit here. Why would you want to? At some point, whatever constant you like will imply an inequality that will only hold above some constant. If you pick $2$, for instance, then you need $x>\sqrt 2$. $\endgroup$ – lulu Mar 2 at 21:09
1
$\begingroup$

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)$.

$\endgroup$
0
$\begingroup$

$ 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.

$\endgroup$
0
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.