Any formal treatment of complexity often begins with this. The concept here is easy. Let be an algorithm with input (We assume this from here onwards). Then, let be a complexity measure of , such that . Define:

Let us exemplify what we mean here. Suppose takes to run. Then, we can say that is or . You can check that it satisfies the limit above. We cannot, however, talk about it being .

This notation is infrequently used. However, it can be good to know what it means.

Menaka Lashitha Bandara 2005-04-18