Computational complexity: Difference between revisions

Revision as of 17:36, 9 June 2021

Revision as of 14:20, 20 July 2021

Line 27:

==Complexity as a function of input size==

:''For clarity, only{{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.