CONCEPT · Novice
Time complexity
also Big-O · runtime
A coarse bound on how the number of primitive operations grows with input size. In contests it is a filter: illegal algorithms are rejected before they are written.
Intuition
Ignore constants until the bound is legal. n² at n = 2e5 is not 'a bit slow' — it does not exist in a 2-second limit.
When to reach for it
- First 20 seconds of reading a problem
- Choosing between DP states
- Estimating a nested loop you just wrote
Usual pits
- Assuming 1e8 ops/s in slow languages without a margin
- Forgetting that log n from a heavy set<> can still TLE in tight limits
- Hiding an extra linear factor inside a 'log n' helper