Time and Space Complexity in Interviews: What You Actually Get Asked
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 recognized it | "Because that's the complexity of sorting" |
| "Can you do better?" | Whether you know what the bound is | Silence, or trying random optimizations |
The best answer to the third is often "no, and here is why". Recognizing 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 memorizing
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 memorize it, which is the entire point of the question.
The same habit carries to tables. For a two-dimensional dynamic programming solution the time is the number of cells times the work per cell, and the space depends on whether you keep the whole table or only the last row. The 2-D dynamic programming guide works one table cell by cell and says when the full table is worth its space.
"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 optimizations 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. The arrays and hashing pattern guide shows the trade in code.
How to practice 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. To have the follow-up asked for you, run a coding mock interview with an AI interviewer, which asks about your solution as you write it.
More Articles
Graph Algorithms in Interviews: From Theory to Implementation
March 25, 2026 · 14 min read
What to Do When You Get Stuck in a Coding Interview
July 1, 2026 · 9 min read
Why LeetCode Alone Won't Get You Hired (And What to Do Instead)
July 10, 2026 · 10 min read