# Complexity Theory

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 5n3+2n2-n+1003 machine cycles, where n is the size of the input, we will simplify this to O(n3) (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.