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.