Time Complexity Interview Guide

Nobody in a technical interview asks you to recite the formal definition of Big O. What they actually want is much narrower and much more practical: can you look at your own solution, right after you've written it, and say — correctly, out loud — how its cost grows as the input does. This guide assumes you already know roughly what O(n) means (if not, start with Big O Notation Explained with Real Examples) and focuses entirely on the interview-specific part: the cheat sheets worth memorizing, the space-complexity question almost everyone forgets, and two fully worked examples talked through the way you'd actually say them out loud.

What's actually being evaluated

Not whether you land on the exact right notation on the first try — whether your reasoning is sound. "This is O(n) because we're a single pass over the input, no nested lookups" is a good answer even phrased informally. "It's O(n log n), I think, because sorting" with no follow-up when asked which part is doing the sorting and why that's log n is a bad answer even if the final letter grade happens to be correct. Interviewers are listening for the causal chain — this line runs n times, and each run does this much work — not the label at the end of it.

Data structure operations — the cheat sheet worth memorizing

This table comes up constantly, directly or indirectly, because most interview problems are really "which data structure turns this O(n) or O(n²) operation into something cheaper."

Two rows are worth saying out loud with the caveat attached, because interviewers specifically listen for it: hash map operations are O(1) on average — the worst case, driven by hash collisions, is O(n), and a good answer mentions that instead of stating O(1) as an unconditional guarantee. And "balanced BST" is doing real work in that row — an unbalanced tree degrades to a linked list in the worst case (imagine inserting already-sorted data), which is O(n), not O(log n). If a question just says "BST" with no balance guarantee, that worst case is worth naming.

Algorithms — the ones that come up over and over

The question everyone forgets: what about space?

A correct time complexity with no space complexity is half an answer, and most interviews ask for both. The part that actually catches people isn't counting extra arrays or hash maps — it's remembering that the recursion call stack is space too. A recursive function with no explicit data structure at all can still be O(n) space, because there are n stack frames alive at once while the recursion is at its deepest.

Reversing a linked list makes this concrete:

// Iterative — O(n) time, O(1) space
function reverseIterative(head) {
  let prev = null;
  while (head) {
    const next = head.next;
    head.next = prev;
    prev = head;
    head = next;
  }
  return prev;
}

// Recursive — O(n) time, O(n) space
function reverseRecursive(head, prev = null) {
  if (!head) return prev;
  const next = head.next;
  head.next = prev;
  return reverseRecursive(next, head); // n stack frames deep at the bottom of the recursion
}

Same input, same output, identical O(n) time — and a real space complexity difference that only shows up if you think about the call stack specifically, not just what variables the function allocates. Recursion vs Iteration Visualizer shows this literally, as an actual call stack growing and shrinking frame by frame next to an iterative version that never uses more than a constant number of variables. See Space Complexity Explained for more of this — including a case where the recursion-depth cost and the time-complexity cost of the same function land in completely different classes.

A framework for saying it out loud

1. Name the input size variable(s) first. If there are two inputs of different sizes (two arrays, a tree and a target list), they need different variable names — O(n) when there are really two independent inputs is a common, avoidable imprecision. Two inputs of sizes m and n processed in two separate passes is O(m + n), not O(n); processed in a nested loop it's O(m × n).
2. Walk the code in the order it runs, not the order it's written — identify every loop and every recursive call, and what each one does per iteration.
3. State time complexity, tied directly back to step 2: "one loop over n, O(1) work per iteration, so O(n)."
4. State space complexity — auxiliary space (what the algorithm allocates beyond its input), explicitly including recursion depth if there is any.
5. Name best/worst/average case if they differ — a hash-map-based solution that's O(n) average and O(n²) worst case is a more complete and more impressive answer than just "O(n)."
6. If you started with a worse solution, say so and say why the better one works — interviewers generally want to see that reasoning explicitly, not just the destination.

Worked example: Two Sum

Given an array and a target, return the indices of two numbers that add up to it. A reasonable first answer:

function twoSumBruteForce(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
}

Said out loud: "For each element, I'm checking it against every element after it — that's a nested loop over the same input, O(n²) time, O(1) extra space." Then the improvement:

function twoSumHashMap(nums, target) {
  const seen = new Map(); // value -> index
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) return [seen.get(complement), i];
    seen.set(nums[i], i);
  }
}

"Instead of scanning ahead for a match, I store what I've already seen and check the map for the complement — one pass, O(1) average lookup per element, so O(n) time overall. That costs O(n) space for the map, so this is a time/space tradeoff, not a free win." That last sentence is the difference between an answer that states a number and one that demonstrates understanding of what changed and why.

Worked example: naive vs. memoized Fibonacci

function fib(n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } looks like it should be O(n) — there's only one visible parameter — but every call that isn't a base case makes two more, and neither knows the other might recompute the same value. fib(15) alone makes 1,973 calls, verified by actually running the trace in Recursion vs Iteration Visualizer — O(2ⁿ). Caching each result the first time it's computed drops that same call to 29 calls: O(n) time, at the cost of O(n) space for the cache — another explicit time/space tradeoff worth naming, not just the smaller number.

Common mistakes worth avoiding

• Stating hash map operations as O(1) with no caveat. It's an average case; say so.
• Forgetting the call stack counts as space for any recursive solution, even one that allocates nothing else.
• Adding when you should multiply, or the reverse. Two loops in a row over the same input add: O(n) + O(n) = O(n). A loop inside a loop multiplies: O(n) × O(n) = O(n²). Mixing these up in either direction is one of the most common live-interview slips — see Big O Notation Explained with Real Examples for the exact pattern to watch for, including the version that doesn't look nested at all.
• Assuming O(n log n) always beats O(n²). Asymptotically, yes — at the input sizes a real interview problem usually specifies, not necessarily. See When O(n²) Becomes a Problem for where that line actually sits, and why two real production sort implementations deliberately fall back to an O(n²) algorithm below a size threshold.
• Not stating an assumption before relying on it — "binary search works here because the array's sorted" is a sentence worth saying explicitly, not left implicit.

Try it yourself

Big O Calculator and Complexity Visualizer build intuition for how fast these classes actually diverge, and Recursion vs Iteration Visualizer makes the call-stack space question from this guide directly visible instead of abstract. For hands-on practice recognizing complexity in real algorithms, Sorting Algorithm Visualizer, Search Algorithm Visualizer, Graph Traversal Visualizer, and Shortest Path Visualizer all run real algorithms step by step with real counted operations. All of them run entirely in your browser.

FAQ

Do I need to simplify — drop constants and lower-order terms?

Yes, the same way the formal notation does — O(2n + 5) is stated as O(n). See Algorithm Complexity Explained for why that's mathematically justified, not just a convention.

What if I only have a brute-force solution?

State its complexity correctly and say what you'd try next and why — a candidate who ships a correct O(n²) solution and can name a specific O(n) idea worth exploring reads better than one who goes silent trying to jump straight to the optimal answer.

Is time complexity or space complexity more important to get right?

Whichever one the problem is actually bottlenecked on — most interview problems care most about time, but a surprising number specifically probe space (in-place array problems, constant-space constraints), and missing that a recursive solution isn't actually O(1) space is a common way to lose an otherwise-correct answer.

Is anything on this page tracking or sending data anywhere?

No — this is a static guide, and every tool linked from it runs entirely in your browser.