How to solve a Big O problem involving a simple polynomial 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?
 A: 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)$.
A: 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.
A: 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).
