Proving big-O notation?

Question

$2n^2 \in O(n^2-19n)$

This was proven in my lecture notes but it didn't make sense to me.

I tried solving for c like this:

$n_0 = 1$

$2n^2 ≤ c * n^2 - 19n$

$2 ≤ c * (1-19)$

$2 ≤ c * -18$

$-36 \leq c$, but $c$ has to be a positive constant.

Answer 1

You have to show that there exists a $c > 0$ and an $N$ such that, for $n > N$ you have $2n^2 < c(n^2-19n)$.

This is the same as $2n < cn-19c$ or $n(c-2) > 19c$.

This needs $c > 2$, so lets choose $c=3$ and see how large $n$ needs to be.

For $ c=3$, this is $n > 19\cdot 3 = 57$, so $N=60$ certainly works.

Therefore, for $n > 60$ and $c=3$ we have $2n^2 < c(n^2-19n)$.

Note that we do not have to find the best $N$ and $c$ - finding any that works is enough.

With enough practice, you will be able to look at problems like this and say "anything fixed times n is smaller than $n^2$ so we can ignore the 19n. Then anything fixed times $n^2$ is $O(n^2)$ so that is true."

Answer 2

Often it is easier to consider a quotient and study its behaviour as $n\to \infty$. Here you have

$$\frac{n^2-19n}{2n^2} = \frac{1}{2}- \frac{19}{2n}\geq \frac{1}{4} \quad \text{for} \quad \frac{19}{2n} \leq \frac{1}{4} \iff n \geq 38$$

So, you have for $n \geq N=38$: $\boxed{2n^2 \leq 4(n^2-19n)}$ which means exactly that $2n^2 \in O(n^2-19n)$.