The $ \Theta$ measure

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

    $\displaystyle 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.



Menaka Lashitha Bandara 2005-04-18