complexity theory

Complexity theory is a part of the theory of computation that has to with the resources needed to solve a given problem. The most common resources are time (how many steps it takes to solve a problem) and space (how much memory it takes to solve a problem). Complexity theory differs from computability theory, which deals with whether a problem can be solved at all, regardless of the resources required.