The Big-O measure

This is the more common of the complexity measures. And as you will see, you can somewhat value this measure when we work with complexity classes. Let us define big-O:

$$f \in O(g(n)) \iff f(n) < Ag(n), A \in \mathbb{R}$$

$$\iff \frac{f(n)}{g(n)} < A$$

$$\iff \lim_{n \to\infty} \frac{f(n)}{g(n)} < A$$

$$\iff \lim_{n \to\infty} \frac{f(n)}{g(n)} = c, c \in \mathbb{R}$$

This is less stronger than the little-O notation. Here, if $f(n) = n^3 + 3 n^2 + 1$, it is valid to say that $f$ is $O(n^3)$ or $O(n^5)$. It is, however, invalid to say $f$ is $O(\log(n))$ or $O(n)$.

This notation is important because it allows us to naturally build complexity classes as subsets of each other. We illustrate this in one of the following sections.