Computational complexity: Difference between revisions

Revision as of 00:29, 8 September 2022

Revision as of 00:31, 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 andrequirements of [[space complexity|space]] (memory) and [[time complexity|time]] (cycles) requirements. 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.