*Complexity theory* concerns itself with two kinds of measures: time and space.

*Time complexity* is a measure of how long a computation takes to execute. For a
Turing machine, this could be measured as the number of moves required to perform a
computation. For a digital computer, it could be measured as the number of machine cycles
required for the computation.

*Space complexity* is a measure of how much storage is required for a computation.
For a Turing machine, the obvious measure is the number of tape squared used; for a
digital computer, the number of bytes used.

Both of these measures are functions of a single input parameter, the *size of the
input.* Again, this can be defined in terms of squares or bytes.

For any given input size, different inputs typically require different amounts of space
and time. Hence we can discuss for either the *average case* or for the *worst
case.* Usually we are interested in worst-case complexity because

- It may difficult or impossible to define an "average" case. For many problems,
the notion of "average case" doesn't even make sense.

- It is usually much easier to compute worst-case complexity.

In complexity theory we generally subject our equations to some extreme
simplifications. For example, if a given algorithm takes exactly 5n^{3}+2n^{2}-n+1003
machine cycles, where n is the size of the input, we will simplify this to O(n^{3})
*(read: Order n-cubed).* This is called an *order statistic.* Specifically, we:

- Drop all terms except the highest-ordered one, and

- Drop the coefficient of the highest-ordered term.

Justifications for this procedure are:

- For very large values of n, the effect of the highest-order term completely swamps the
contribution of lower-ordered term. We are interested in large values of n because, from a
strictly practical point of view, it is the large problems that give us trouble. Small
problems are almost always feasible to compute.

- Tweaking the code can improve the coefficients, but the order statistic is a function of the algorithm itself.