The $\Theta$ measure

This is an important measure. Let us define it, and then illustrate it's importance. Define:

$$f \in \Theta(g(n)) \iff \lim_{n \to\infty} \frac{f(n)}{g(n)} = c, c \neq 0$$

We can easily show that $\Theta(g(n)) \subseteq O(g(n))$. So, in a sense $\Theta(g(n))$ is a minimal measure. More often that not, in a practical circumstance, we use $O(g(n))$ as if we are really talking about $\Theta(g(n))$. It is rare that someone would say that $f(n) = n^2 + 1$ is $O(n^3)$ in a practical sense, although technically, it is in fact true.

One would argue, that from a purely mathematical and logical perspective, we should only use the $\Theta$ measure. With a little extra work, we can easily construct the complexity classes from this, rather than naturally letting the classes follow by the use of the Big-O measure. But more about that to follow.