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

    $\displaystyle P = \left\{\Phi: C(\Phi) \in O(n^p), p \in \mathbb{Z}\right\}$

This essentially means that $ P$ 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 $ P$-time.

Note, that although the theoretical aspiration is to distinguish the polynomial (easy) algorithms from the others, an algorithm which is $ O(n^{10})$ is still quite slow. Usually, we like linear - $ O(n)$ or quadratic - $ O(n^2)$ algorithms.

Menaka Lashitha Bandara 2005-04-18