Mathematically, we define this set to be programs such that:

This essentially means that are the set of algorithms which are Polynomial in the complexity measure. Usually, this is time, and hence, we say that the algorithm is in -time.

Note, that although the theoretical aspiration is to distinguish the polynomial (easy) algorithms from the others, an algorithm which is is still quite slow. Usually, we like linear - or quadratic - algorithms.

Menaka Lashitha Bandara 2005-04-18