Imagine you have 1 million users. An O(nΒ²) algorithm takes 1 trillion operations on their data β that's a 30-minute request. An O(n log n) algorithm takes about 20 million operations β under a second.
Big-O is not about measuring exact speed. It describes how an algorithm's cost grows as the input grows. You're answering: If I double the input, what happens to the work?
The scale that matters most in interviews:
| Notation | Name | 10 items | 10 000 items | 1 000 000 items |
|---|---|---|---|---|
| O(1) | Constant | 1 | 1 | 1 |
| O(log n) | Logarithmic | 3 | 14 | 20 |
| O(n) | Linear | 10 | 10 000 | 1 000 000 |
| O(n log n) | Log-linear | 33 | 133 000 | 20 000 000 |
| O(nΒ²) | Quadratic | 100 | 100 000 000 | 10ΒΉΒ² |
Most interview problems want O(n) or O(n log n). An O(nΒ²) brute force is almost always improvable.