Time complexity

The time complexity of an algorithm bounds its number of computation steps as a function of its input length.

An algorithm runs in polynomial time when its running time is at most $O(n^k)$ for some constant $k$, where $n$ is the input length.

$\mathbf{P}$ is the class of decision problems decidable by a deterministic computation in polynomial time.

$\mathbf{NP}$ is the class of decision problems whose positive instances have polynomial-length certificates verifiable in polynomial time. Equivalently, it is polynomial time on a nondeterministic computation.

A certificate for a positive instance is a polynomial-length string that makes a polynomial-time verifier accept that instance.