| CSC403: Order of growth [5/5] | |
| Name | Function | Intuition |
|---|---|---|
| Constant | O(1) | Data independent |
| Logarithmic | O(lg(n)) | Iteratively cut in half |
| Linear | O(n) | Iterate once for each item |
| Linearithmic | O(n * lg(n)) | Nested iteration: once linear, once logarithmic |
| Quadratic | O(n^2) | Nested iteration: twice linear |
| Cubic | O(n^3) | Nested iteration: three times linear |
| Exponential | O(2^n) | Combinations |
| Factorial | O(n!) | Permutations |
Image from 8 time complexities that every programmer should know by Adrian Mejia