Computational complexity: Difference between revisions

Revision as of 08:01, 8 September 2022

Revision as of 14:59, 8 September 2022

Line 1:

{{Short description|Amount of resources to perform an algorithm}}

{{no footnotes|date=December 2017}}

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 requirements of [[timespace complexity|timespace]] (memory/storage) and [[spacetime complexity|memorytime]] requirements(cycles). The complexity of a [[computational problem|problem]] is the complexity of the best algorithms that allow solving the problem.

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]]. 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. Moreover, for designing efficient algorithms, it is often fundamental to compare the complexity of a specific algorithm to the complexity of the problem to be solved. Also, in most cases, the only thing that is known about the complexity of a problem is that it is lower than the complexity of the most efficient known algorithms. Therefore, there is a large overlap between analysis of algorithms and complexity theory.