cppreference.com > Complexity
Complexity
There are different measurements of the speed of any given algorithm. Given an input size of N, they can be described as follows:
| Name | Speed | Description | Formula |
|---|---|---|---|
| exponential time | slow | takes an amount of time proportional to a constant raised to the Nth power | K^N |
| polynomial time | fast | takes an amount of time proportional to N raised to some constant power | N^K |
| linear time | faster | takes an amount of time directly proportional to N | K * N |
| logarithmic time | much faster | takes an amount of time proportional to the logarithm of N | K * log(N) |
| constant time | fastest | takes a fixed amount of time, no matter how large the input is | K |