# Disproving big O polynomial inequality

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?

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

• Can you please elaborate on your hint? how did you get 8n^3? – Saad May 25 '17 at 16:24
• @Saad Is it clear now? – Robert Z May 25 '17 at 16:26
• To be honest not really. i get that $$n^3 > 2n,$$n^3 > 10 but how does this relate to the question? Like the way i was thinking about it was manipulating the inequality and getting a value for n. – Saad May 25 '17 at 16:32
• It is not necessary to "solve" the inequality. We have a "big" term $10n^3$ and we can split it to balance the other terms. – Robert Z May 25 '17 at 16:37
• So i were to disprove this, then this would be the way to do it? Also now i understand what you did with the 10n^3. – Saad May 25 '17 at 16:41

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$

• I just want to solve it by manipulating the inequality. – Saad May 25 '17 at 16:23
• ok, I understand. then Robert Z gave you a nice answer for that :) But keep in mind that using limits is usually a nice and easy way to show O-notions (and $\Omega$ notions as well) – Mickey May 25 '17 at 16:26
• We are still learning that in class. I am trying this question which we did in class but couldn't get the idea from our professor. – Saad May 25 '17 at 16:34

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

• Should that not be there exists c such that there exists n...for the definition of big oh? – Saad May 25 '17 at 17:09
• @Saad about what statement are you talking? (2)? – miracle173 May 25 '17 at 17:54
• yes (2), i was just looking on the internet and it seems it should be "there exists" for both c and n and in negation it becomes "for every". – Saad May 25 '17 at 17:57
• No, the inequality must hold for all $n$. "There exist an $n$ and there exist a $c$" such that a property holds does not make sense. You want not make a statement about the value of $f$ at a single $n$ but you want to make a statement how $f$ behaves on the whole (or almost the whole) set of natural numbers. – miracle173 May 25 '17 at 18:12
• @Saad: added a link to wiki and some explanations. The previous comment was to answer your question but I forgot to add your name. – miracle173 May 25 '17 at 19:53