Questions
18 of 29
Rank the common Big-O complexities from best to worst.
Difficulty: 3/10
Ordering of Common Complexity Classes
Complexity classes are ranked by how quickly their growth rate increases as input size n grows. Lower growth rates scale better for large inputs, even if they might be slower for very small n due to constant factors.
- 1
O(1) - Constant
- 2
O(log n) - Logarithmic
- 3
O(n) - Linear
- 4
O(n log n) - Linearithmic
- 5
O(n^2) - Quadratic
- 6
O(n^3) - Cubic
- 7
O(2^n) - Exponential
- 8
O(n!) - Factorial
In practice, for very small inputs an O(n^2) algorithm with low constant factors can outperform an O(n log n) algorithm with high constant factors, which is why algorithms like Insertion Sort are sometimes used as a base case in hybrid sorts like Timsort or Introsort.
Follow-up Questions
- Why might an algorithm with worse Big-O still perform better in practice?