Computational complexity: Difference between revisions

Revision as of 22:27, 25 March 2020

Revision as of 22:32, 25 March 2020

Line 3:

In [[computer science]], the '''computational complexity''' or simply '''complexity''' of an [[algorithm]] is the amount of resources required to run it. Particular focus is given to [[time complexity|time]] and [[space complexity|memory]] requirements.

As the amount of resources required to run an algorithm generally varies with the input size of the input, the complexity is typically expressed as a function {{math|''n'' → ''f''(''n'')}}, where {{math|''n''}} is the size of the input and {{math|''f''(''n'')}} is either the [[worst-case complexity]] (the maximum of the amount of resources that are needed over all inputs of size {{math|''n''}}) or the [[average-case complexity]] (the average of the amount of resources over all inputs of size {{math|''n''}}). [[Time complexity]] is generally expressed as the number of required elementary operations on an input of size {{math|''n''}}, where elementary operations are assumed to take a constant amount of time on a given computer and change only by a constant factor when run on a different computer. [[Space complexity]] is generally expressed as the amount of [[computer memory|memory]] required by an algorithm on an input of size {{math|''n''}}.

The study of the complexity of explicitly given algorithms is called [[analysis of algorithms]], while the study of the complexity of problems is called [[computational complexity theory]]. Clearly, both areas are highly related, as the complexity of an algorithm is always an [[upper bound]] on the complexity of the problem solved by this algorithm.