Editing Computational complexity (section)

==Complexity as a function of input size==
{{hatnote|Only time complexity is considered in this section, but everything applies (with slight modifications) to the complexity with respect to other resources}}
It is impossible to count the number of steps of an algorithm on all possible inputs. As the complexity generally increases with the size of the input, the complexity is typically expressed as a function of the size {{math|''n''}} (in [[bit]]s) of the input, and therefore, the complexity is a function of {{math|''n''}}. However, the complexity of an algorithm may vary dramatically for different inputs of the same size. Therefore, several complexity functions are commonly used.

The [[worst-case complexity]] is the maximum of the complexity over all inputs of size {{mvar|n}}, and the [[average-case complexity]] is the average of the complexity over all inputs of size {{mvar|n}} (this makes sense, as the number of possible inputs of a given size is finite). Generally, when "complexity" is used without being further specified, this is the worst-case time complexity that is considered.