The eight typical growth classes are the "alphabet" of complexity. We remember each one through an example.
The order of the classes
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
The polynomial classes are considered practical; 2ⁿ and n! are only usable for small n.
| Class | Example |
|---|---|
O(1) | list indexing, dict lookup |
O(log n) | binary search in a sorted list |
O(n) | one pass over a list, the maximum |
O(n log n) | merge sort, sorted |
O(n²) | two nested loops, all pairs |
O(n³) | naive matrix multiplication |
O(2ⁿ) | all subsets of a set |
O(n!) | all permutations |
import math
def steps(n):
return {
"O(1)": 1,
"O(log n)": math.ceil(math.log2(n)),
"O(n)": n,
"O(n log n)": n * math.ceil(math.log2(n)),
"O(n^2)": n ** 2,
"O(n^3)": n ** 3,
"O(2^n)": 2 ** n,
"O(n!)": math.factorial(n),
}
for name, value in steps(10).items():
print(f"{name:<11}{value:>10,}")O(1) 1
O(log n) 4
O(n) 10
O(n log n) 40
O(n^2) 100
O(n^3) 1,000
O(2^n) 1,024
O(n!) 3,628,800