Time Complexity Classes (P)

Running time, big-O order, and the class of polynomial-time problems.

The idea

Time complexity classifies problems by how the running time of an algorithm grows with the size of its input. A stopwatch reading reflects the hardware, so we count steps instead: the running time $t(n)$ is the number of steps the algorithm takes on the worst input of size $n$.

We keep only how $t$ grows. Doubling the clock speed halves every $t(n)$ without making any problem easier, so we write $t(n) = O(g(n))$ to mean $t(n) \le c\,g(n)$ for some constant $c$ and all large $n$. Constant factors and lower-order terms disappear, and a step count of $3n^{2} + 5n + 7$ becomes $O(n^{2})$.

The standard boundary between feasible and infeasible is polynomial time:

$\mathrm{P} = \{\,\text{problems decided in time } O(n^{k}) \text{ for a constant } k\,\}.$

We draw the line there because the class is robust. Polynomials are closed under sums and products, so a polynomial-time routine called a polynomial number of times still runs in polynomial time, and replacing one reasonable machine model with another leaves $\mathrm{P}$ unchanged. Outside it sit running times such as $2^{n}$ and $n!$, which eventually exceed every fixed power of $n$, however large its exponent.

Ways to work on it

• Walkthrough. Asymptotic order, polynomial time, and why P is closed under composition.
• Practice. Read off the polynomial order of a running time.
• Hardest. Polynomial versus exponential growth and what it means for membership in P.

Not sure where to start? Take the ten-question placement test.