# Computational complexity theory

# Computational complexity theory

- A realm of study that seeks to identify categories of algorithms and classify them according to their efficiency
- efficiency is measured with regard to resource usage, i.e. CPU/memory load and time
- parallels theoretical computer science fields like “algorithmic analysis” and “computability theory”
- differs from algorithmic analysis in that computational complexity theory is more general and, rather than seeking to analyze the efficiency of a particular algorithm, seeks to quantify and qualify all of the possible algorithms that could be used to solve a particular problem
- this particularly includes very difficult problems that cannot be solved efficiently

- the classes used to categorize problems by complexity (known as “complexity classes”) are generally bounded by some time/space constraint
- For example, the complexity class “
*P*” is bounded by the constraint “polynomial time”, i.e. `O(poly(n))`

, meaning that any problems which require more time/space than this will graduate to the next class
- More on complexity classes ↗