Exercise I
Consider the following function $T(n)$ describes the precise running time of an algorithm:
$$ T(n) = 3n^2 - 100n + 6 $$
Exercise Prove $T(n) \in O(n^2)$.
Solution
We can choose $c=3$ and $n_0=1$ for the definition of Big Oh to hold.
$$ 3n^2 - 100n + 6 \le 3n^2 $$
Recall the choice of $n_0$ and $c$ are not unique.
There can be many (actually, infinitely many) different combinations of $n_0$ and $c$ that would make the proof work. It depends on what inequalities you use while doing the upper-bounding.
Exercise Prove $T(n) \in O(n^3)$.
Solution
We can choose $c=1$ and $n_0=1$ for the definition of Big Oh to hold.
$$ 3n^2 - 100n + 6 \le n^3 $$
Big-Oh expresses an upper bound but does not necessarily provide a precise description of the worst-case running time, i.e. it is not necessarily a tight upper bound.
Exercise Prove $T(n) \notin O(n)$.
Solution
There is no $c$ and $n_0$ where we can write $c \times n \ge 3n^2$ when $n > c$.