The time complexity describes the amount of computer time it takes to run an algorithm. It is estimated by counting the number of elementary operations performed by the algorithm. Since an algorithm’s running time may vary among different inputs of the same size, one commonly considers the worst-case time. Algorithmic complexities are classified according to the type of function appearing in the big O notation. Here are some examples:
| Name |
Time complexity |
| Constant time |
$\mathcal{O}(1) $ |
| Logarithmic time |
$\mathcal{O}(\log n) $ |
| Linear time |
$\mathcal{O}(n) $ |
| Linearithmic time |
$\mathcal{O}(n \log n)$ |
| Quadratic time |
$\mathcal{O}(n^2) $ |
| Polynomial time |
$2^{\mathcal{O}(\log n)} = poly(n)$ |
| Exponential time |
$2^{poly(n)}$ |
Multiplication algorithms
Schoolbook multiplication
Consider this example $102 \times 257$: