Overview
Complexity communication is explaining the time and space cost of your solution clearly and correctly: naming the variables, stating the dominant term, and justifying it from the code. Interviewers expect it for every solution, and many ask for it before you code.
A good explanation has three parts: define the variables (n = number of nodes, m = length of word), give the result for time and space separately, and point to the reason ('each index is pushed and popped at most once, so the nested loop is O(n) total'). Mentioning trade-offs and alternatives shows depth.
A good courier does not just say 'fast'. They say 'same day within the city, two days nationally, because packages go through one regional hub'. A complexity explanation gives the estimate, the conditions, and the reason.
When to use it
- When presenting your approach before coding.
- After coding, as part of the wrap-up.
- When comparing two approaches or answering 'can we do better?'.
- When explaining a design decision in code review or design docs.
Problem patterns it solves
Recognize it when: two inputs of different sizes, grids, graphs.
- 200. Number of Islands: O(R x C)
- 207. Course Schedule: O(V + E)
- 72. Edit Distance: O(m x n)
Recognize it when: nested loops where the inner work is bounded overall.
- 739. Daily Temperatures
- 3. Longest Substring Without Repeating Characters
- 146. LRU Cache
Recognize it when: generating all subsets, permutations, or paths.
- 78. Subsets: O(n x 2^n)
- 46. Permutations: O(n x n!)
Recognize it when: call stack depth counts as space.
- 104. Maximum Depth of Binary Tree: O(h)
- 509. Fibonacci Number
Where it is used in real software
Engineers justify data structure choices with expected cost at scale: 'lookups are O(1) with a hash index; range queries would need a B-tree'.
Knowing a job is O(n log n) lets teams predict runtime when data grows 10x.
Reviewers ask 'what is the complexity of this loop over all users?' to catch scaling problems early.
Key terms
- Variables
- Name every size that matters: n, m, V, E, k, L.
- Dominant term
- The fastest-growing part of the total cost.
- Auxiliary space
- Extra memory used beyond the input (state whether output counts).
- Amortized
- Average cost per operation over a sequence.
A template for explaining complexity
- 1Define the variables
'Let n be the length of the array and k the window size.'
- 2State time with the reason
'Time is O(n log n): sorting dominates, and the two-pointer pass is O(n).'
- 3State space with the reason
'Space is O(n) for the hash map; O(1) extra if we exclude the output.'
- 4Mention the best, average, or worst case if they differ
'Average O(1) per lookup, worst case O(n) with heavy collisions.'
- 5Compare with alternatives
'A heap would be O(n log k); quickselect is O(n) average but O(n^2) worst.'
Weak vs strong explanations
Solution: sliding window with a hash map for longest substring without repeats
| Quality | Explanation |
|---|---|
| Weak | It's O(n), I think, because there's a loop. |
| Better | Time O(n), space O(n). |
| Strong | n = length of s. Time O(n): right moves n times and left only moves forward, so at most 2n pointer moves. Space O(min(n, alphabet)) for the map, which is O(1) for a fixed 128-character alphabet. |
NOWQuality: Weak | Explanation: It's O(n), I think, because there's a loop.
The strong answer names the variable, gives the bound, and justifies the nested loop with an amortized argument. It also refines space using the alphabet size, which shows real understanding.
Implementation
/** * 347. Top K Frequent Elements * * n = nums.length, u = number of distinct values (u <= n) * Time: O(n) counting is O(n); bucket fill is O(u); collecting is O(n) at most * Space: O(n) frequency map O(u) + buckets O(n) * Alternative: min-heap of size k gives O(n log k) time, O(u + k) space */function topKFrequent(nums, k) { const freq = new Map(); for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1); const buckets = Array.from({ length: nums.length + 1 }, () => []); for (const [value, count] of freq) buckets[count].push(value); const result = []; for (let f = nums.length; f > 0 && result.length < k; f--) result.push(...buckets[f]); return result.slice(0, k);}Complexity and performance
Variables, time, space, reason.
Adjacency list traversal.
Every cell once.
Trade-offs
Give the tight bound and one-line justification; save derivations for when the interviewer asks.
State the worst case by default, and mention expected or amortized bounds when they are the reason a solution is good.
Variants and related techniques
When two solutions share a bound, mention practical factors: cache friendliness, allocations, recursion overhead.
Translate to operations: 'n = 10^5, so O(n log n) is about 1.7 million operations, well within limits.'
Common mistakes
- Collapsing different inputs into one n.
Fix: O(m x n) for two strings, not O(n^2).
- Forgetting recursion stack space.
Fix: Recursive DFS is O(depth) space even without extra data structures.
- Ignoring hidden costs.
Fix: String slicing, array copying, sorting inside loops, and includes are not free.
Interview questions
How would you explain the complexity of BFS on a grid?
With R rows and C columns, each cell is enqueued at most once and checks four neighbors, so time is O(R x C). The queue and visited set are O(R x C) in the worst case.
Is sorting-based O(n log n) always worse than hash-based O(n)?
Asymptotically yes, but hash maps have larger constants and O(n) memory. Sorting in place may use less memory and be competitive for moderate n.
Practice problems
| Problem | Difficulty | What it trains |
|---|---|---|
| Explain 10 past solutions out loud | Easy | Variables, time, space, reason. |
| 347. Top K Frequent Elements | Medium | Compare three approaches. |
| 200. Number of Islands | Medium | Grid and recursion space. |
| 146. LRU Cache | Medium | Explain O(1) per operation. |