Given a problem and a computational model, the complexity of the problem with respect to the model is a function of the input size. Complexity functions may measure different quantities, such as time or space:
- The time complexity measures how much time is required by the model to solve the problem, given an input.
- The space complexity measure how much memory space is required by the model to solve the problem, given an input.
As a measure, the complexity can be defined as a function:
c = f(n)
n is the input size.
Usually, the complexity is classified with the analytical form of
f(n). For example, if
f(n) = n, the complexity is linear with respect to
f(n) = n2, the complexity is quadratic; and, if
f(n) = 2n, the complexity is exponential.