How to Explain Time Complexity in an Interview

How do you explain Big-O time complexity in a coding interview?

Walk through the loops and the work per iteration, multiply them, and state the dominant term. Say it out loud twice: once when you propose your approach, once after coding to verify. The grade is for whether you can reason about cost — the actual letter is downstream. Saying "O(n log n) because of the sort plus a linear sweep" is the move; "I think it's fast" is not.

The structure of a complexity claim

Every Big-O statement in an interview should follow this shape:

"[Dominant term] because of [structural reason]. [Smaller terms] from [the rest of the work]. So the total is [dominant term]."

Examples:

• "O(n log n) because of the sort. The two-pointer sweep after is O(n). So total is O(n log n)."
• "O(n) — single pass, constant work per element thanks to the hash map."
• "O(n × m) — n is the number of words, m is the longest word length, and I'm doing constant work per character."

This shape forces you to justify the answer, not assert it. Interviewers ding asserted complexities because they can't tell whether you reasoned or guessed. A justified O(n²) often scores higher than an unjustified O(n).

How to count loops and work-per-step

The reliable mechanical method:

1. Identify each loop. Note whether it iterates n times, log n times, sqrt n times, or some function of the input. A while loop counts too.
2. For each loop, ask: what work is done per iteration? Is the inner work constant, or does it depend on input size?
3. Multiply nested loops, add sequential loops. Two nested O(n) loops = O(n²). Two sequential O(n) loops = O(n) (since 2n = O(n)).
4. Keep only the dominant term. O(n² + n log n + n) = O(n²). Don't list the smaller terms in the final statement — but feel free to mention them in your walkthrough as proof of work.

The trap most candidates fall into is hidden iteration. s in substring_set looks like constant work but is O(k) where k is the substring length. list.insert(0, x) looks like one operation but is O(n) because everything shifts. Per the Pragmatic Engineer's writing on technical interviews, hidden-iteration bugs are one of the top reasons candidates state wrong complexities for code that actually works.

Amortized complexity — when it matters

Some operations look variable-cost but average to constant over many calls:

• Dynamic array append: O(1) amortized, O(n) on the resize step.
• Hash map insert/lookup: O(1) amortized, O(n) worst case if every key collides.
• Stack with lazy compaction: O(1) amortized when the compaction work is paid in by the inserts.

State the amortized analysis when your solution depends on it. "I'm using a hash map, so lookups are O(1) amortized — the worst case is O(n) but that's vanishingly unlikely for random keys" is the kind of nuance that separates a passing answer from a strong one.

Space complexity is half the grade

Many candidates state time and forget space, which costs them a chunk of the rubric. Two sources of space to track:

1. Auxiliary data structures. The hash map, the visited set, the stack you're maintaining. These are usually obvious.
2. Recursion / call stack. Less obvious. Recursive DFS on a balanced binary tree is O(log n) space; on a degenerate (linked-list-shaped) tree it's O(n). Always say which case you're claiming.

Per the Indeed Career Guide's writing on technical interview rubrics, space complexity is one of the most-skipped items on interview evaluation forms — meaning candidates who explicitly state space tend to score noticeably higher than candidates with identical solutions who only stated time.

When complexity is dominated by something subtle

Three classics where the dominant cost isn't the obvious loop: string concatenation in a loop (result += s[i] is O(n²) in many languages — each += copies the whole string; use a list and join at the end), sorting a list of strings (O(n log n × k) where k is the average string length, because each comparison is O(k)), and set membership on a list (x in some_list is O(n), not O(1) — converting to a set first is almost always worth it).

When one of these dominates, name it explicitly: "The concatenation in the loop is actually O(n²) — let me switch to a list-and-join, which gets us back to O(n)." Catching these out loud is one of the strongest signals you can give in a coding round. It says: I think about cost, not just correctness.

About the author: Alex Chen is the founder of InterviewChamp.AI and writes about the modern tech interview from the inside — what changed, what works for new grads, and where the old playbook fails.