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:

This is less stronger than the little-O notation. Here, if , it is valid to say that is or . It is, however, invalid to say is or .

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.

Menaka Lashitha Bandara 2005-04-18