Big O describes how time or space grows relative to input size n — the foundation for comparing algorithms.
| Notation | Name | Example |
|---|---|---|
| O(1) | Constant | Array index access |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Linear search |
| O(n log n) | Linearithmic | Merge sort |
| O(n²) | Quadratic | Bubble sort |
| O(2^n) | Exponential | Recursive subsets |
| O(n!) | Factorial | Permutations |
# n=1000 comparisons:
# O(1) = 1
# O(log n) = 10
# O(n) = 1,000
# O(n log n)= 10,000
# O(n^2) = 1,000,000
# O(2^n) = astronomical
# Rules
# Drop constants: O(2n) -> O(n)
# Drop lower terms: O(n^2 + n) -> O(n^2)
# Best/Avg/Worst case all matter