Disproving big O polynomial inequality

Question

I am stuck on a simple question that asks me to disprove $$f(n)=10n^3−2n−10$$ is not $O(n^2)$ without using any properties of $O$-notation. If I were to solve this, how would I go about this. I do understand that:

We need to prove $$cn^2 < 10n^3−2n−10$$ where $c$ being a positive integer. And next I need to manipulate the inequality but I am not sure how that would prove the inequality at hand?

Can anyone help me understand these type of equations?

Answer 1

Given $c>0$, for $n>n_0:=\max(c/7,2)$, $$10n^3−2n−10=7n^3+(n^3−2n)+(2n^3−10)>7n\cdot n^2+0+0>cn^2$$ because $n^3>2n$, $2n^3>10$, and $7n>c$.

Answer 2

What do you mean without using any properties of O-notion?

You can show that: $\lim_{n\to \infty} \frac{10n^3-2n-10}{n^2} = \infty$

Answer 3

Wikipedia says:

$$ f(x)=O(g(x)) \; x \to \infty \tag{W1} $$ is defined as $$\exists M: \; \exists x_0: \; \lvert f(x) \lvert\le M\lvert g(x)\lvert,\; \forall x > x_0 \tag{W2}$$

If we replace $M$ and $x_0$ by $$C:=\max\{x_0,M\} \tag{W3}$$ and get the simpler equivalent definition

$$\exists C: \; \lvert f(x) \lvert\le C \lvert g(x)\lvert,\; \forall x > C \tag{W4}$$

If we restrict $x$ to $\mathbb{N}$ and if $g(n) \ne 0, \; \forall n\in \mathbb{N}$ we can set $$c:=\max\left\{\left\lvert \frac{f(1)}{g(1)} \right\lvert, \left\lvert \frac{f(2)}{g(2)} \right\lvert, \ldots, \left\lvert \frac{f(\lfloor c\rfloor)}{g(\lfloor c\rfloor)} \right\lvert, C\right\} \tag{W5}$$ and we finally get

$$\exists c: \; \lvert f(n) \lvert \le c \lvert g(n)\lvert,\; \forall n \in \mathbb{N} \tag{W6}$$ if $g(n)\ne 0, \; \forall n \in \mathbb{N}$.

---

You cannot show something about the big $O$ notation without using its properties.

$$f(n)=O(n)\tag{1}$$

means, that $$\exists c \in \mathbb{R^+}:\; \forall n \in \mathbb{N}: \; f(n)\le c\cdot n\tag{2}$$

The negation of this sentence is

$$\lnot\;(\exists c \in \mathbb{R^+}:\; \forall n \in \mathbb{N}: \; f(n) \le c\cdot n) \tag{3}$$ which is equivalent to

$$\forall c \in \mathbb{R^+}: \; \exists n \mathbb{N}: \; f(n)>c \tag{4}$$

For our $f$ this means we have to show

$$\forall c \in \mathbb{R^+}: \; \exists n \mathbb{N}: \; cn^2 < 10n^3−2n−10\tag{5}$$ or $$\forall c \in \mathbb{R^+}: \; \exists n \mathbb{N}: \; 10n^3−cn^2-2n−10>0 \tag{6}$$

This is true, we can select $$n:=c+2 \tag{7}$$ then we have $$ 10n^3−cn^2-2n−10 \\= 10(c+2)^3−c(c+2)^2-2(c+2)−10 \\=9c^3+56c^2+114c+66\\ >0 \tag{8}$$ because $c>0$.