Editing Complexity class (section)

===Resource bounds===
Complexity classes group computational problems by their resource requirements. To do this, computational problems are differentiated by [[upper bound]]s on the maximum amount of resources that the most efficient algorithm takes to solve them. More specifically, complexity classes are concerned with the ''rate of growth'' in the resources required to solve particular computational problems as the input size increases. For example, the amount of time it takes to solve problems in the complexity class '''[[P (complexity)|P]]''' grows at a [[polynomial]] rate as the input size increases, which is comparatively slow compared to problems in the exponential complexity class '''[[EXPTIME]]''' (or more accurately, for problems in '''EXPTIME''' that are outside of '''P''', since <math>\mathsf{P}\subseteq\mathsf{EXPTIME}</math>).

Note that the study of complexity classes is intended primarily to understand the ''inherent'' complexity required to solve computational problems. Complexity theorists are thus generally concerned with finding the smallest complexity class that a problem falls into and are therefore concerned with identifying which class a computational problem falls into using the ''most efficient'' algorithm. There may be an algorithm, for instance, that solves a particular problem in exponential time, but if the most efficient algorithm for solving this problem runs in polynomial time then the inherent time complexity of that problem is better described as polynomial.

====Time bounds====
{{Main|Time complexity}}
The [[time complexity]] of an algorithm with respect to the Turing machine model is the number of steps it takes for a Turing machine to run an algorithm on a given input size. Formally, the time complexity for an algorithm implemented with a Turing machine <math>M</math> is defined as the function <math>t_M: \mathbb{N} \to \mathbb{N}</math>, where <math>t_M(n)</math> is the maximum number of steps that <math>M</math> takes on any input of length <math>n</math>.

In computational complexity theory, theoretical computer scientists are concerned less with particular runtime values and more with the general class of functions that the time complexity function falls into. For instance, is the time complexity function a [[polynomial]]? A [[logarithmic function]]? An [[exponential function]]? Or another kind of function? 

====Space bounds====
{{Main|Space complexity}}
The [[space complexity]] of an algorithm with respect to the Turing machine model is the number of cells on the Turing machine's tape that are required to run an algorithm on a given input size. Formally, the space complexity of an algorithm implemented with a Turing machine <math>M</math> is defined as the function <math>s_M: \mathbb{N} \to \mathbb{N}</math>, where <math>s_M(n)</math> is the maximum number of cells that <math>M</math> uses on any input of length <math>n</math>.