When the execution time of a computation, m(n), is no more than a polynomial function of the problem size, n. More formally m(n) = O(n^k) where k is a constant.