Computational complexity: Difference between revisions

Revision as of 04:02, 22 April 2020

Revision as of 04:52, 25 May 2020

Line 5:

As the amount of resources required to run an algorithm generally varies with the 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 [[computational problem|problems]] is called [[computational complexity theory]]. Clearly, bothBoth 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.

==Resources==