How to solve a Big O problem involving a simple polynomial

Question

im stuck as this question involving Big O notation, is it true that?

$$n^2 - 200n - 300 = O(n)$$

What i've tried:

Generally, I dont know problems involving algorithms analysis. I would start assuming that this statement is true. So I would find an $h(n)$ function that is linear and , given a $n_0$.

$$n^2 - 200n - 300 \leq h(n)$$

But i don't know how to do that or if that is even right, any hints or advices?

Answer 1

By definition, taking non negative case, we have $$O(g)=\left\lbrace f: \exists C_f>0, \ \exists N,\ n>N, f \leqslant C_f g\right\rbrace$$

So you have tried to prove, that for some $C>0, \exists N, n>N$ $$n^2 - 200n - 300 \leqslant C n$$ but : $$n^2 - 200n - 300 \leqslant C n \Leftrightarrow n^2 \leqslant (200+C)n +300 \Leftrightarrow \\ \Leftrightarrow n \leqslant 200+C +\frac{300}{n}\quad(1)$$ Now let's look at right side: when $n>300$, then we have $\frac{300}{n}<1$.

From another hand, as $C>0$, then $0\leqslant \lfloor C \rfloor < \lfloor C \rfloor +1 \in \mathbb{N}$.

So, if we take $n>\max(200+\lfloor C \rfloor +2, 300)$, then we come in contradiction with $(1)$.

Answer 2

Your approach is a good way to start with a problem whose answer you don't know. Is the function $O(n)$? Try to prove that it is.

But you should also try to prove that the function is not $O(n),$ just in case it turns out that it is not $O(n)$ after all.

To prove that a function $f(n)$ is not $O(n),$ you can try proof by contradiction. Specifically, you can assume the function is $O(n)$ and then show that the definition is not satisfied.

Assuming that $n^2 - 200n - 300$ is $O(n),$ as you know, there must be a linear function $h(n)$ and a number $n_0$ such that $n^2 - 200n - 300 \leq h(n)$ whenever $n > n_0.$

In the definitions of $O(n)$ with which I'm familiar, $h(n)$ would have to be some function of the form $kn$ for some positive constant $k.$ That may be what you meant by "linear," but it's good to be explicit about this.

Suppose you had such a function. The constant in that function would have to have some particular value. Whatever that value is, call it $k_0.$ And now the assumption that $n^2 - 200n - 300$ is $O(n)$ has logically implied that there is a number $n_0$ such that

$$n^2 - 200n - 300 \leq k_0 n \quad \text{whenever $n > n_0.$} \tag1$$

Now all you need to do is show a way to find a single number $n$ such that $n > n_0$ and $n^2 - 200n - 300 > k_0 n,$ given whatever values of $k_0$ and $n_0$ might be the ones that supposedly make the statement with the tag $(1)$ true.

Answer 3

It is true, but misleading, since obviously the limit of the ratio diverges. It is better to use a different notation. If $h(n)= O(n)$, the function on RHS, and $g(n)=n^2 -200n-300$, then $g(n)=\omega(h(n))$ (divergence), or $h(n)=o(g(n))$ (convergence to $0$). You can easily show both by taking lower bound in the first case (you need to find constant $c_1$ such that $g(n)\geq c_1n^2$, and an upper bound on $\frac{h(n)}{g(n)}$ (the same constant will do).