0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Can you please elaborate on your hint? how did you get 8n^3? $\endgroup$ – Saad May 25 '17 at 16:24
  • $\begingroup$ @Saad Is it clear now? $\endgroup$ – Robert Z May 25 '17 at 16:26
  • $\begingroup$ 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. $\endgroup$ – Saad May 25 '17 at 16:32
  • $\begingroup$ 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. $\endgroup$ – Robert Z May 25 '17 at 16:37
  • $\begingroup$ 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. $\endgroup$ – Saad May 25 '17 at 16:41
0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ I just want to solve it by manipulating the inequality. $\endgroup$ – Saad May 25 '17 at 16:23
  • $\begingroup$ 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) $\endgroup$ – Mickey May 25 '17 at 16:26
  • $\begingroup$ 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. $\endgroup$ – Saad May 25 '17 at 16:34
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Should that not be there exists c such that there exists n...for the definition of big oh? $\endgroup$ – Saad May 25 '17 at 17:09
  • $\begingroup$ @Saad about what statement are you talking? (2)? $\endgroup$ – miracle173 May 25 '17 at 17:54
  • $\begingroup$ 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". $\endgroup$ – Saad May 25 '17 at 17:57
  • $\begingroup$ 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. $\endgroup$ – miracle173 May 25 '17 at 18:12
  • $\begingroup$ @Saad: added a link to wiki and some explanations. The previous comment was to answer your question but I forgot to add your name. $\endgroup$ – miracle173 May 25 '17 at 19:53

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.