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.