What Big-O really says
Big-O describes how runtime grows as input grows — not the exact time. We drop constants and lower-order terms because, at scale, they don't matter.
Rules of thumb
- A loop over the input is O(n).
- A loop inside a loop over the same input is O(n²).
- Halving the search space each step is O(log n).
- Sorting is usually O(n log n).
Key idea
When an interviewer says "can you do better?", they almost always mean: can you drop a factor of n — e.g. replace a nested scan (O(n²)) with a hash set (O(n))?