Examples for proofs with $O(\ldots)$

Assume we want to prove that $5n = O(4n-10)$. We need to find $c>0$ and $n_0$ such that $5n \leq c (4n -10)$ for all $n \ge n_0$.

Now, if we would need to prove that $5n = O(4n)$ then that would be easier, since we could simply choose $c = \frac{5}{4}$. We would immediately get $5n \le c 4n$, since actually $5n = c 4n$. But we will need to deal with the '-10' on the right hand side. We will do this, by picking a suitable $n_0$ such that '-10' is small compared to $4n$. So now lets actually prove the original statement:

proof: If we choose $n_0 = 10$, then for $n \ge n_0$ we have $4n - 10 = (3n + n) - 10 = 3n + (n - 10) \ge 3n$. Now choose $c = \frac{5}{3}$. We get $0 < 5n = c 3n \le 4n - 10$ for all $n \ge n_0$, which is what we had to prove.

The proof technique is useful if we want to prove a statement of the type $f(n) = O(g(n))$. But what if we want to prove that $f(n) = O(g(n))$ is a false statement? Now if we for instance want to prove that for instance $n^2 = O(n)$ is false, we can use a proof by contradiction. This means that we prove that the statement is false by assuming that it is true, and then leading this to a false statement. Then we know that our original assumption must have been already false.

Often enough such a proof ends with a statement, that as such is not false, but that contradicts our original assumption. This is just as good to conclude that our orginal assumption must have been wrong; and essentially we also end up with a false statement, because the original statement with the statement that is wrong together form a false statement. Lets try this:

proof (by contradiction): Suppose there is a $c>0$ and an $n_0$ such that $n^2 \le c n$ for all $n \ge n_0$. This is equivalent to $n \le c$. But for large enough $n$, we eventually have $n > c$ no matter how large we picked the constant $c$. A contradiction. So $n^2 = O(n)$ is false.

In [ ]: