Step 1 of 6
Big-O in practice
Big-O describes how running time grows with the input size n, ignoring constant factors:
| Complexity | n = 1,000 | n = 1,000,000 | Typical example |
|---|---|---|---|
| O(1) | 1 | 1 | array index, hash lookup |
| O(log n) | 10 | 20 | binary search |
| O(n) | 1,000 | 1,000,000 | one pass over the data |
| O(n log n) | 10,000 | 20,000,000 | good sorting |
| O(n²) | 1,000,000 | 1,000,000,000,000 | comparing every pair |
A computer does roughly 10⁸ to 10⁹ simple operations per second. So at a million items, O(n²) takes hours while O(n log n) takes milliseconds. Interviews test this, and so does production traffic.
The most common fix for O(n²) is trading memory for time: remember what you've seen in a hash set, which has O(1) average lookup.
Your turn: write bool has_duplicate(const std::vector<int>& v) in O(n). The hidden test uses 200,000 numbers, so comparing every pair will run out of time.