Big-O questions in interviews are rarely "define Big-O." They are "what is the time and space complexity of the solution you just wrote, and can you do better?" The skill being tested is whether you can reason about how your code scales and say it out loud without hand-waving. This guide shows you how to derive complexity in seconds, map input constraints to a target complexity before you even code, and communicate the analysis the way interviewers score it.
What interviewers are actually testing
In our mock interviews, the complexity question almost never comes as a standalone trivia prompt. It arrives at three moments: right after you propose an approach ("what's the complexity of that?"), right after you finish coding ("walk me through the time and space"), and as a nudge toward optimization ("can you get it under O(n^2)?"). Each moment tests something different. The first checks whether you can evaluate a plan before sinking 15 minutes into it. The second checks whether you actually understand the code you wrote. The third checks whether you know which complexity class the problem is really asking for.
The failure modes are predictable. Candidates blurt out "O(n)" for a nested loop, forget the space taken by recursion, or quote the average case when the interviewer wanted the worst case. Getting this right is a cheap signal to send, and getting it wrong undercuts an otherwise correct solution. It is one of the most common coding interview mistakes precisely because it is so avoidable.
Derive time complexity in four steps
You do not need to memorize a table. You need a repeatable process.
-
Count the dominant loop structure. One pass over the input is O(n). A loop inside a loop over the same input is O(n^2). A loop that halves the search space each iteration is O(log n). Nested loops over different inputs are O(n * m), not O(n^2). Keep the sizes separate; interviewers notice when you collapse two different inputs into one variable.
-
Account for work inside each iteration. A loop that does a hash lookup per step stays O(n). A loop that does a sort or a linear scan per step is O(n^2) or O(n log n). The body matters as much as the loop count. This is where "Integer to English Words" trips people up: it looks trivial, but you should be able to state that it runs in O(d) where d is the number of digits, since each three-digit chunk does constant work.
-
Handle recursion with the tree, not vibes. For recursive solutions, multiply the number of calls by the work per call. A binary tree traversal like "Find Duplicate Subtrees" visits each of n nodes once, but if you serialize each subtree by concatenating child strings, each node can contribute O(n) work in the worst case, pushing the naive version to O(n^2). Switching to an id-based serialization with a hash map brings it back to O(n). Being able to explain that jump is exactly the optimization signal interviewers want.
-
Simplify: drop constants and lower-order terms. O(2n + 5) is O(n). O(n^2 + n) is O(n^2). Say the simplified form, but be ready to defend the raw count if pushed.
Read the constraints before you write code
The fastest complexity analysts do it in reverse. They look at the input bounds and deduce the target complexity before coding a line. The rule of thumb from competitive programming is that a modern judge handles roughly 10^8 operations per second, and interviewers implicitly expect solutions that would run comfortably under that. After figuring out the number of operations that can be performed, you search for the right complexity by looking at the constraints given in the problem.
Use this cheat table as your starting guess:
| Input size (n) | Likely target complexity | Typical approach |
|---|---|---|
| n <= 12 | O(n!) or O(2^n) | permutations, brute-force backtracking |
| n <= 25 | O(2^n) | subset enumeration, bitmask |
| n <= 5,000 | O(n^2) | nested loops, basic DP |
| n <= 100,000 | O(n log n) | sort, heap, binary search |
| n <= 10,000,000 | O(n) or O(log n) | single pass, two pointers, math |
Two problems from our question bank show the extremes. "Minimum Moves to Spread Stones Over Grid" fixes the board at 3x3 with exactly nine stones, so an exponential search over permutations of source and destination cells is not just acceptable, it is the intended solution. The tiny bound is a hint. On the other end, "Maximum Number of Consecutive Values You Can Make" wants you to sort the coins and sweep once, which is O(n log n), because the array can be large enough that an exponential subset check would time out.
The complexity classes worth knowing cold
Most interview problems land in a handful of buckets. Here is where our sample problems sit, so you can anchor the abstract classes to something concrete.
- O(1) constant. "Minimum Amount of Time to Fill Cups" reduces to a closed-form comparison between the largest requirement and the sum of the other two. No loop over input size. When you spot a math shortcut, say "this is O(1)" with confidence; it is a strong signal. Practice more of these in Math interview questions.
- O(n) linear. Single-pass DP like "Domino and Tromino Tiling" builds an answer for width n from the previous two or three states, so time is O(n) and space collapses to O(1) if you keep only the last few values.
- O(n log n). Anything that sorts first, including the greedy sweep in "Maximum Number of Consecutive Values You Can Make."
- O(n^2) and pseudo-polynomial DP. "Number of Ways to Stay in the Same Place After Some Steps" runs in O(steps * min(steps, arrLen)) because you never need positions farther than the number of steps allows. Bounding the state space is the whole trick, and it is the kind of nuance that separates a clean answer from "it's some DP thing." Build the muscle with dynamic programming questions.
- Higher polynomial. "Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree" is a staff-level problem where you rebuild an MST while forcing or banning each edge, giving roughly O(E^2 * alpha(V)) with union-find. Nobody expects you to nail the alpha term, but you should be able to explain why it is quadratic in the number of edges.
Space complexity is the half people forget
When the interviewer asks for complexity, they mean time and space. State both, unprompted. The three sources of space that candidates routinely miss:
- The recursion stack. A DFS on a skewed tree uses O(n) stack space even if you allocate no extra data structures. For "Find Duplicate Subtrees," the hash map of serialized subtrees is also O(n) space, and you should name both.
- The output. Returning all duplicate subtrees or all critical edges can be O(n) or O(E) in the result itself. Some interviewers exclude output from space accounting; ask if it matters.
- Auxiliary structures. A DP table, a visited set, a monotonic stack. Say whether you can compress it. "Domino and Tromino Tiling" is a nice example where the naive O(n) table becomes O(1) with rolling variables, and volunteering that optimization scores points.
Say it out loud the right way
The analysis only counts if you communicate it cleanly. A reliable script: "Time is O(n log n) because I sort the coins, then a single linear pass. Space is O(1) auxiliary if I sort in place, or O(n) if I cannot mutate the input. Worst case and average case are the same here since the sort dominates." That sentence hits the four things graders look for: the class, the reason, the space, and the case distinction.
Two habits make you sound senior. First, always specify worst case unless told otherwise, and flag when average and worst diverge (hash collisions, quicksort partitioning). Second, tie the complexity back to the constraints: "n is up to 10^5, so O(n^2) would be about 10^10 operations, too slow, which is why I moved to the heap." That closes the loop between the bound and your choice, and it is the reasoning that makes an interviewer trust the rest of your solution. You can drill this narration in AI mock interviews that push back on vague answers the way a real interviewer does.
FAQ
Do I state best, average, or worst case in an interview?
Default to worst case unless the interviewer specifies otherwise, because that is what scaling guarantees depend on. Call out when average and worst diverge, such as hash tables (O(1) average, O(n) worst on collisions) or quicksort (O(n log n) average, O(n^2) worst). Naming the distinction unprompted signals depth.
Should I count the space used by the output?
Mention it and ask. Many interviewers count only auxiliary space, treating the required output as free, but some include it. State both, for example "O(1) auxiliary, plus O(k) for the returned list," so you are covered either way.
How do I analyze recursive solutions quickly?
Multiply the number of recursive calls by the work done per call, and add the maximum recursion depth as stack space. For divide and conquer, use the recurrence: splitting into two halves with linear merge work gives O(n log n). Drawing the call tree for two levels usually reveals the pattern.
What if I genuinely cannot tell the complexity?
Reason out loud from the loop structure instead of guessing a final answer. Say what each loop and each operation inside it costs, then combine them. Interviewers reward visible reasoning over a confident wrong number, and they will often nudge you toward the right term.