Data Structures & Algorithms · Complexity
Big-O: how code scales
Why matching 1M trades with a nested loop takes hours, and with a dict takes a second.
Step 1 of 5 · 1. Growth rates15 min read ·
1. Growth rates
| Big-O | Name | Example | 1M items ≈ steps |
|---|---|---|---|
| O(1) | constant | dict lookup | 1 |
| O(log n) | logarithmic | binary search | 20 |
| O(n) | linear | scan a list | 1,000,000 |
| O(n log n) | linearithmic | sort | 20,000,000 |
| O(n²) | quadratic | nested loop match | 1,000,000,000,000 |
Next: 2. The recon example