Computational complexity refers to the amount of resources required to solve a type of problem by systematic application of an algorithm. Resources that can be considered include the amount of communications, gates in a circuit, or the number of processors. Because the size of the particular input to a problem will affect the amount of resources necessary, measures of complexity will have to take into account this difference. As such, they can be reported as a function of the input size. As a basic example, consider the problem of sorting an array of random numbers. Take two arrays of different sizes. Intuitively, the larger one will require more steps when using the same method. Additionally, comparisons of complexity across a range of input sizes may not be consistent – that is, an algorithm may be considered to be less complex than others for small inputs, but the same comparison may not hold for larger input sizes. Depending on starting points, iterative application of algorithms may not cover the same trajectory to the same solution even if the input to the problem is identical. One way of addressing this variability is to compare the upper and lower bounds of complexity (worst and best case scenarios, respectively) and average values. Returning to our example, consider the case when the arrays are randomly populated. There is a probability, however small, that either or both of the arrays will be populated already sorted. In this case, it is possible that the larger array needs less sorting than the smaller one.

Last modified

• 11/29/2018

Creator

• David O'Brien
• Mark Caswell
• David Chen

DOI

• https://doi.org/10.21985/N2XN1T

Keyword

• Computational
• Complexity

Rights statement

• In Copyright