# Polynomial time

In computational complexity theory, **polynomial time** refers to the computation time of a problem where the time, *m*(*n*), is no greater than a polynomial function of the problem size, *n*.

Written mathematically, *m*(*n*) = O(*n*^{k}) where *k* is a constant (which may depend on the problem).

Mathematicians sometimes use the notion of "polynomial time on the length of the input" as a definition of a "fast" computation, as opposed to "super-polynomial time", which is anything slower than that. Exponential time is one example of a super-polynomial time.

The complexity class of decision problems that can be solved on a deterministic sequential machine in polynomial time is known as **P**. The class of decision problems that can be verified in polynomial time is known as **NP**. Equivalently, NP is the class of decision problems that can be solved in
polynomial time on a non-deterministic Turing machine (NP stands for
**N**ondeterministic **P**olynomial time).

## Subclasses of polynomial time

- Linear time: O(
*n*) - Quadratic time: O(
*n*^{2}) - Cubic time: O(
*n*^{3})