Time and Space Complexity in Interviews: What You Actually Get Asked
Alex Chen
Senior Engineer
Nobody fails a coding interview for not knowing the formal definition of big O notation. People fail for saying "it's O(n log n)" in a flat voice and being unable to say which part of their own code costs the log n. Time and space complexity in an interview is not a recall question. It is a question about whether you understand the code you just wrote.
What actually gets asked
Three questions, in this order, in almost every round. The first is the one candidates rehearse; the second and third are where the marks move.
| The question | What is being checked | Weak answer |
|---|---|---|
| "What is the complexity?" | Can you state it at all | A guess that happens to be right |
| "Where does that come from?" | Whether you derived it or recognised it | "Because that's the complexity of sorting" |
| "Can you do better?" | Whether you know what the bound is | Silence, or trying random optimisations |
The best answer to the third is often "no, and here is why". Recognising that you must read every element, so O(n) is the floor, is a stronger signal than producing a faster algorithm by luck.
The one table worth memorising
Complexity classes are abstract until you attach them to numbers. This is what the difference actually costs at interview-sized inputs, assuming roughly a hundred million simple operations a second.
| Complexity | n = 1,000 | n = 100,000 | n = 10,000,000 |
|---|---|---|---|
| O(log n) | instant | instant | instant |
| O(n) | instant | ~1 ms | ~0.1 s |
| O(n log n) | instant | ~17 ms | ~2 s |
| O(n²) | ~10 ms | ~100 s | years |
| O(2ⁿ) | beyond the universe | - | - |
This table also works in reverse, and that is its real use in an interview. If the constraints say n is up to 100,000, an O(n²) solution is not merely inelegant, it is wrong for the stated input, and saying so out loud is a strong signal before you have written any code.
Derive it, do not recall it
The habit that separates strong answers is narrating the derivation from your own code rather than pattern matching to a known result. Out loud, it sounds like this: the outer loop runs n times, the lookup inside is constant on average, the sort at the start is n log n, so the sort dominates and the whole thing is n log n.
Four short clauses. It takes fifteen seconds and it is immediately obvious to the interviewer that you did not memorise it, which is the entire point of the question.
"Simplicity is prerequisite for reliability."
- Edsger W. Dijkstra, EWD498 (1975)
Space complexity, which everybody forgets
Volunteer the space cost without being asked. It takes one sentence and it is a reliable differentiator because most candidates only mention time. Three things people miss when they do try:
| Easy to miss | The correct reading |
|---|---|
| Recursion | The call stack is space: depth d costs O(d) |
| The output | Usually excluded by convention, but say which convention you are using |
| Sorting in place | Many library sorts are not O(1) space |
| Strings | Slicing copies in most languages, so it is not free |
🔑 The trade you should name
Most interview optimisations are the same trade: spend memory to buy time, usually with a hash map. Saying "I can drop this to O(n) time by holding an O(n) map, which is worth it here because n is small" is the trade-off sentence interviewers are listening for, and it works on a surprising number of problems.
How to practise this specifically
Take ten problems you have already solved. Do not resolve them. Just open each one and say the complexity out loud, with the derivation, in under twenty seconds. You will find two or three where you know the answer but cannot explain it, and those are precisely the ones where a follow-up question would have caught you.
It is a thirty minute exercise, it needs no new problems, and it closes one of the most commonly probed gaps in a technical interview.
More Articles
Graph Algorithms in Interviews: From Theory to Implementation
March 25, 2026 · 14 min read
From LeetCode Grinder to Interview-Ready: The Practice Method Nobody Talks About
June 18, 2025 · 14 min read
How to Answer "Tell Me About Yourself" in a Technical Interview
June 20, 2026 · 8 min read