Questions tagged

complexity-theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty. Particularly common in programming is *amortized analysis* for time or space

Given a problem and a computational model, the complexity of the problem with respect to the model is a function of the input size. Complexity functions may measure different quantities, such as time or space:

- The time complexity measures how much time is required by the model to solve the problem, given an input.
- The space complexity measure how much memory space is required by the model to solve the problem, given an input.

As a measure, the complexity can be defined as a function:

```
c = f(n)
```

where `n`

is the input size.

Usually, the complexity is classified with the analytical form of `f(n)`

. For example, if `f(n) = n`

, the complexity is *linear* with respect to `n`

; if `f(n) = n`

, the complexity is ^{2}*quadratic*; and, if `f(n) = 2`

, the complexity is ^{n}*exponential*.