Time complexity
Contents
- Constant
- Logarithmic
- Linear
- Sub- and super-linear
- Polynomial
- Example: nub
- Improvement
- Exponential
The only way to really know how fast code runs is to run it. But we can also achieve a great deal through reasoning. Especially for “collections” libraries,A few examples of collections libraries: containers, unordered-containers, vector it is common to describe the efficiency of an operation by giving a rough idea of the relationship between the number of elements in a collection and the time required to compute the operation.
The terminology for this comes from the field of asymptotic analysis, which contains a lot to learn. But for everyday programming, these are the top five words you should be familiar with:
| Mathematically | Informally | |
|---|---|---|
| Constant | 1 | Fast |
| Logarithmic | log n | Pretty fast |
| Linear | n | Noticeable |
| Polynomial | n2 | Unpleasant |
| Exponential | 2n | Unusable |