Use for questions about the efficiency of a specific algorithm (the amount of resources, such as running time or memory, that it requires) or for questions about the efficiency of any algorithm solving a given problem.
Computational complexity is a part of theoretical computer science that answers questions about how efficient an algorithm is:
- How much time (as a function of the size of the input) does the algorithm take to produce its output?
- How much space (such as computer memory) does it require?
- How much of some other resource does it consume? (For example, this can be the size of a logic circuit solving the problem, or the number of bits of randomness used by a probabilistic algorithm.)
We can similarly ask about the computational complexity of any algorithm that solves a given problem.
Often, very specific details of these answers (such as constant factors or additive terms) depend on specific details such as the computer you're using. To help deal with this, we often stick to determining the asymptotic complexity of an algorithm: see asymptotics for more details.
A major problem in computational complexity is the P versus NP problem, which asks if a certain class of problems can be solved by an algorithm that runs in a number of steps that's a polynomial function of the input size.
