Big O Complexity Reference
Operations counts at various input sizes.
Operations at n = 1,000
| Complexity | What it is | Operations |
|---|---|---|
| O(1) | Constant | 1 |
| O(log n) | Logarithmic (binary search) | 10 |
| O(n) | Linear (loop) | 1,000 |
| O(n log n) | Linearithmic (mergesort) | 9,966 |
| O(n²) | Quadratic (nested loops) | 1,000,000 |
| O(n³) | Cubic | 1,000,000,000 |
| O(2ⁿ) | Exponential | 1.13e+15 |
| O(n!) | Factorial | 2.43e+18 |
Common operations
- Array index accessO(1)
- Hash map lookup (avg)O(1)
- Array push / pop endO(1)
- Array shift / unshiftO(n)
- Linear searchO(n)
- Binary search (sorted)O(log n)
- Merge sort, quick sort, heap sortO(n log n)
- Bubble sort, insertion sortO(n²)
- Find duplicate (nested loop)O(n²)
- Subset sum (brute force)O(2ⁿ)
- Traveling salesman (brute force)O(n!)
Big O describes how an algorithm scales with input size, not absolute speed. O(n²) on a small list can be faster than O(n log n) on the same list - constants matter when n is small. The crossover usually happens around n ≈ 100.
About
Pick n. The tool shows how many operations each Big O complexity (constant, log, linear, n log n, quadratic, exponential, factorial) would do. Plus a quick reference of common operations and their complexities.
How to use
- Enter input size n.
- Compare row-by-row.
FAQ
Why does my O(n²) sort beat my O(n log n) for small lists?+
Big O ignores constants. For n < 50 or so, insertion sort often beats merge sort because the constant factor is smaller. Real sort implementations (like V8's TimSort) switch to insertion sort for small subarrays.