Lesson 08 · 16 min
Time & Space Complexity (Plain English)
Big-O intuition so you can defend your solution in interviews.
Complexity without fear
Time — how work grows with n
| Pattern | Big-O | Example |
|---|---|---|
| One loop | O(n) | Scan array |
| Nested loops i,j | O(n²) | All pairs |
| Sort | O(n log n) | sort(vec) |
| Hash lookup | O(1) avg | unordered_map |
Space
Extra arrays/maps you allocate (not counting input, usually).
Two Sum hash map: O(n) time, O(n) space.
Target for n = 1e5
Rough interview budget ~ 1e8 ops/sec mental model:
- O(n) and O(n log n) OK
- O(n²) often TLE
How to say it
"I scan once while storing seen values in a hash map, so linear time and linear extra memory."
Rules to remember
- State time and space after every solution.
- Sorting then two pointers: O(n log n) time.
- n=1e5 → avoid plain O(n²).
- Trade space for time with hashing when needed.
Check yourself
1. Best expected time for Two Sum with hash map?