Big-O notation
Big-O notation is the prevalent notation to represent algorithmic complexity. It gives an upper bound on complexity and hence it signifies the worst-case performance of the algorithm. With such a notation, it’s easy to compare different algorithms because the notation tells clearly how the algorithm scales when input size increases. This is often called the order of growth.
- Constant runtime is represented by O(1)
- linear growth is O(n)
- logarithmic growth is O(log n)
- log-linear growth is O(n log n)
- quadratic growth is O(n2)
- exponential growth is O(2n)
- factorial growth is O(n!)