Talking About Big-O in a Coding Interview Without Fumbling

Almost every coding interview ends with "what's the time and space complexity?" Many candidates who solved the problem cleanly then lose points by guessing, hedging or getting space wrong. A short, repeatable way of answering fixes that.

State it at three moments

Brute force, before coding: "The naive approach checks every pair, O(n²) time, O(1) space." This frames the improvement you're about to make.
Your plan: "With a hash map I can get O(n) time at the cost of O(n) space." Now the interviewer knows the target.
After coding, verified against the code: point at the loops and data structures that produce each term.

Justify, don't just declare

"O(n log n)" on its own sounds memorised. "We sort once, O(n log n), then a single pass, O(n), so the sort dominates" shows you derived it. Name what n is, too, especially when there are two inputs: O(m + n) and O(m · n) are very different answers.

Costs people forget

String building. Repeated s += c in a loop can be O(n²) in some languages; a list-and-join is O(n).
Slicing and copying. arr[1:] in a recursive call copies; that adds O(n) per call.
Recursion stack. A DFS with no explicit data structure still uses O(h) space for the call stack.
Hidden library calls. list.remove, in on a list, and indexOf are linear.
Output size. Generating all subsets is O(2ⁿ · n) no matter how clever the loop is: say so.

Quick reference

Pattern	Typical time
Single pass / two pointers	O(n)
Sort then scan	O(n log n)
Binary search on sorted data	O(log n)
Heap of size k over n items	O(n log k)
BFS/DFS on a graph	O(V + E)
Backtracking over subsets	O(2ⁿ)

When asked "can you do better?"

Ask yourself what the lower bound is. If you must look at every element, you can't beat O(n); say so confidently rather than hunting for a trick that doesn't exist. If the bottleneck is repeated lookups, a hash map or precomputation usually helps. If it's sorting, ask whether the input range is small enough for counting sort.

Disclosure: I'm with the team at Linkjob AI, a real-time interview assistant. This guide is general and product-independent.