AI can write the code, but you still get asked what it costs. These should come instantly.
Know the common costs by heart. Hash lookups are O(1) on average, sorting is O(n log n), a heap push is O(log n), and binary search is O(log n).
For scale, a modern machine handles very roughly 10^8 simple operations a second. So n = 10^6 is fine at O(n log n), and hopeless at O(n²).
Top k from m items costs O(m log k) with a heap, and O(m log m) with a full sort.
- What does sorting cost, in time?
- O(n log n).
- What's the cost of a hash map lookup?
- O(1) on average, and O(n) in the worst case.
- What's the cost of a heap push or pop?
- O(log n). Peeking at the top is O(1).
- Top k of m items with a heap?
- O(m log k) time and O(k) extra space.
- Roughly how many simple operations per second?
- About 10^8, as a rule of thumb for quick estimates.
- Largest n that's reasonable for O(n²)?
- Around 10^4, since that's about 10^8 operations.