Time & space complexity, defended live

Why "I know Big-O" is not the skill

Every candidate who has studied for interviews can define O(n) versus O(n²) versus O(log n) on a whiteboard. That definition is not what gets tested. What gets tested is whether you can look at code you wrote ninety seconds ago, correctly identify its complexity without prompting, and hold up when the interviewer asks "are you sure" or "what if the input were sorted." That is a live reasoning skill, and it is graded separately from whether your solution is correct — a correct, silent solution scores worse on this dimension than a correct solution with its complexity narrated unprompted.

Deriving complexity from code you just wrote

The mechanical version: count nested loops (each independent nesting level multiplies), check whether recursion branches (branching factor raised to the depth, unless memoized), and note any operations with non-constant cost hiding inside a loop — a list.pop(0) in Python or an array .shift() in JavaScript is O(n), not O(1), and doing it inside a loop silently turns an apparent O(n) solution into O(n²). That last one is a specific, common trap: candidates state O(n) confidently because they only counted the visible loop, missing the hidden linear cost inside a single line.

The habit worth building: after finishing any solution, spend five seconds scanning for exactly these three things — nested loops, recursive branching, and any built-in operation whose cost you have not actually confirmed — before stating a number.

Amortized complexity: when nested loops are not O(n²)

Sliding window and monotonic stack solutions both contain what looks like a nested loop (a while inside a for), and candidates who pattern-match on "nested loop = O(n²)" state the wrong complexity confidently. The actual argument: track how many times the inner loop can execute across the entire run of the algorithm, not per outer iteration. In sliding window, the left pointer only ever moves forward, so its total movement across the whole run is bounded by n — making the combined cost O(n), not O(n²), even though the code has two loops.

Say this explicitly when it applies: "this looks like O(n²) because of the nested loop, but the inner pointer only moves forward and never resets, so the total work across the whole run is O(n)." That sentence is worth more than getting the number right by instinct, because it demonstrates the reasoning is repeatable on a problem you have not seen before.

Space complexity gets skipped — do not skip it

Most candidates state time complexity unprompted and only mention space complexity if asked directly. Stating both without being asked is a small, cheap signal of thoroughness. It also sets up the most common and most valuable follow-up question in the entire interview: "can you do this with less space?" Being ready for that question — knowing whether your solution's space cost is actually reducible, and being honest when it is not — matters more than getting to O(1) space on every problem.

Handling "can you do better?"

When an interviewer asks for a faster or leaner solution, the worst response is silence followed by a guess. The better response names what the current solution's bottleneck actually is ("the nested loop is what makes this O(n²) — the inner loop is re-scanning elements I've already seen") before proposing a fix. Naming the bottleneck first shows the improvement is reasoned, not recalled from a similar problem. If there genuinely is no better approach, saying so — and explaining why the lower bound holds — is a stronger answer than inventing a fake optimization under pressure.

This complements Thinking Out Loud — complexity narration is one specific, high-value slice of the broader habit of saying what you are doing and why, not just doing it silently.