Computational complexity: Difference between revisions

Revision as of 01:24, 26 March 2020

Revision as of 07:36, 26 March 2020

Line 11:

The resource that is most commonly considered is time. When "complexity" is used without qualification, this generally means time complexity.

The usual units of time (seconds, minutes etc.) are not used in [[computational complexity theory|complexity theory]] because they are too dependent on the choice of a specific computer and on the evolution of technology. For instance, a computer today can execute an algorithm significantly faster than a computer from the 1960s; however, this is not an intrinsic feature of the algorithm but rather a consequence of technological advances in [[computer hardware]]. Complexity theory seeks to quantify the intrinsic time requirements of algorithms, thisthat is, the basic time constraints an algorithm would place on ''any'' computer. This is achieved by counting the number of ''elementary operations'' that are executed during the computation. These operations are assumed to take constant time (that is, not affected by the size of the input) on a given machine, and are often called ''steps''.

===Space===