How do interviewers probe time and space complexity?

In this article

1. Before you start
2. Why interviewers ask this
3. Complexity analysis from first principles
4. The Staff-level answer
5. The rubric
6. Three variants of this question
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page sits in the interview process guide, which explains which rounds exist and who scores what. It teaches one skill used in the coding rounds.

Why interviewers ask this

A correct solution with no cost estimate leaves the interviewer guessing whether you understand why it works. Candidates report being asked for complexity in many forms: the cost of a Python dictionary lookup and of a given duplicate search that uses a set (reported by a senior candidate at a payments company), the time and space of each helper in a stack that returns its maximum in constant time (reported by staff-level candidates), and a quadratic grid solution that the candidate then improved to linear on their own (reported by a staff-level candidate).

A weak answer names one bound ("it's O of n") and stops. A strong answer states time and space, says which case the bound covers, and names the input that hurts. A Staff-level answer also says what it would trade away: more memory for less time, or the reverse.

Complexity analysis from first principles

Time complexity

Time complexity is a description of how the number of basic steps an algorithm performs grows as the input size n grows, written as a simple function of n such as n, n squared or log n, with constants and low-order terms dropped.

Space complexity

Space complexity is a description of how much extra memory an algorithm needs beyond its input as n grows, counting the structures it builds and the call stack its recursion uses.

In plain words

Think of finding a name in a phone book. Reading every page costs time in proportion to the book's size. Opening in the middle and halving the search costs far less. Now compare every name with every other name: that grows with n times n. The analogy breaks in one place: a phone book shows time only, never memory. It is also sorted, which an algorithm's data may not be.

In one precise sentence: big-O notation is an upper bound on how fast a cost function grows, so O(n) says the cost grows no faster than a constant times n. The Princeton course text drops low-order terms in its tilde approximation, and the order of growth also drops the leading constant (Sedgewick and Wayne, section 1.4, accessed 2026-10-26). It says most programs fall into a few such classes.

Step 1: Count the work in terms of n

Time complexity starts by choosing what to count and counting how often it runs. The text names the two factors behind total running time: the cost of each statement and how often each runs (Sedgewick and Wayne, accessed 2026-10-26). In an interview, count the repeated operation, usually a comparison or a lookup.

Take a duplicate search. The nested-loop version compares every pair. On a list of 2,000 distinct items it makes 1,999,000 comparisons; the seen-set version makes 2,000 membership checks.¹ State the result as a formula, not a stopwatch reading: the first is about n times n over two, so O(n²), and the second is O(n) on average.

You now have a time bound for each version. Say the formula, then say what you counted.

The common growth classes, in plain words

A growth class is a family of cost formulas with the same shape. The logarithm, log n, is the number of times you can halve n before one item is left; halving 8 items takes 3 steps. The table lists the classes interviewers expect.

For recursion, multiply the calls per level by the depth. Naive Fibonacci calls itself twice per call, so computing n = 20 makes 21,891 calls, bounded by O(2ⁿ); remembering results (memoizing) cuts it to 39 calls, which is O(n).¹ With two inputs, keep both: comparing a list of n items with a list of m items takes O(n + m) with a set, and a graph search takes O(V + E) for V vertices and E edges. When n is a number's value rather than a length, a loop counting up to it runs that many times, so it is exponential in the number of digits; trial division up to n is an example (such a cost is called pseudo-polynomial).

Step 2: Name the input that makes it slow

A bound belongs to a case, and an interviewer's favorite follow-up asks which one you gave. Best, average and worst case are separate functions of n, and each can have its own big-O bound. Big-O is not "the worst case"; it is an upper bound you can place on any of them.

The dictionary lookup shows it. With a well-spread hash, finding a stored key took one equality check when the dictionary held 800 keys, and a missing key took none. With a deliberately bad hash that returns the same number for every key, the same lookups took 800 equality checks.¹ That is the gap between constant and linear. So a lookup is constant time on average, and linear in the worst case when keys collide, as the Python Wiki time complexity table lists for dictionary lookups.

For the duplicate search, the worst case for the seen-set pass is a list with no duplicates: it must check everything. Name that input out loud.

Step 3: Count extra memory, including the call stack

Space complexity counts memory beyond the input. The nested-loop duplicate search uses a handful of variables, so O(1) extra space. The seen-set version stores every element it has passed, so on a list of 2,000 distinct items the set holds 2,000 entries: O(n) extra space.¹

Recursion has a cost that loops hide. Each active call occupies a stack frame, so a recursive tree traversal uses memory proportional to the tree's height even if it builds nothing. A balanced tree and a tree shaped like a linked list have very different heights, so say which you assume.

State space every time, even if nobody asked. Interviewers often ask for it as the second follow-up, and offering it first shows you track memory unprompted.

Step 4: State the trade-off and how to improve it

Time and space often trade against each other. The seen set buys linear time with linear memory; the nested loop pays quadratic time to keep memory constant. Sorting first is a third option, because duplicates become adjacent and one pass over neighbors finds them: time of order n log n, with extra space depending on the sorting method. Heapsort needs O(1) extra space, while a Python sorted() copy needs O(n).

Say which you would pick and why, using the constraints. Ask about the input limits before choosing: with a small list the simple loop is fine, and with millions of items it is not.

When you start with brute force, say so, give its cost, then name the repeated work you can remove.

1 · Count the work2 · Name the slow input3 · Count memory4 · State the trade-offReplay

Step-by-step description

1. Count the repeated operation in terms of n.
2. Say which case your bound covers.
3. Include structures built and recursion depth.
4. Say what you give up and why.

• Count the repeated operation in terms of n.
• Name the input that makes the solution slow.
• Count extra memory, including the call stack.
• State the trade-off between time and space.

The ratios are the doubling-ratio test the course text describes: double the input, watch how the cost scales (Sedgewick and Wayne, accessed 2026-10-26). A ratio near two means linear; near four means quadratic. Doubling the list size multiplies the nested loop's comparisons by about four, and doubling the list size multiplies the seen-set checks by exactly two.¹

Text description of the diagram

• Doubling the list size multiplies the nested loop's comparisons by about four.
• Doubling the list size multiplies the seen-set checks by exactly two.

The Staff-level answer

What makes it Staff-level: it names the case behind each bound, states space unprompted, and ends on the trade-off rather than on a single number. Say it in order: approach, time with its case, space, worst case, trade-off. Candidates preparing for AI-assisted coding interviews still need this spoken structure, because interviewers still ask you to explain the cost.

The rubric

Three variants of this question

The code is given: what is its complexity?

Read the code for loops and what runs inside each. A single loop with constant-time work inside is O(n); a loop inside a loop over the same data is O(n²); then check every call inside the loops, because a lookup in a list is linear while a lookup in a set is constant on average.

What is the time complexity of a Python dictionary lookup?

Constant time on average and linear in the worst case, when many keys collide, as the Python Wiki time complexity table lists. Give both, and say the average depends on keys spreading well across the table.

You solved it in O(n²): can you do better?

Name the repeated work, usually a scan you do for every item, and replace it with a structure that answers in constant or logarithmic time, such as a set or a sorted order. Then restate time and space. For where such coding questions sit in a hiring process, see what an online assessment is, and for the wider habit of explaining your reasoning, interview skills.

Common mistakes

• "Big-O means worst case." (wrong) Big-O is an upper bound, and each case has its own bound. (right) "This is O(n) on average and O(n²) in the worst case."
• "It's O(1), so it's fast." (wrong) Constant time means the cost does not grow with n, and the constant can still be large. (right) "It does not grow with n; I'd measure the constant if it mattered."
• "Hash lookups are always constant." (wrong) A bad hash made every lookup check every key, 800 of 800 in the run above.¹ (right) "Constant on average, linear if keys collide."
• "Space is zero because I built nothing." (wrong) Recursion uses stack memory proportional to its depth. (right) "O(1) extra space with the loop, O(height) with recursion."
• "I'll skip the trade-off, it's the same thing." (wrong) The interviewer wants to hear what you gave up. (right) "I spend O(n) memory to remove the inner loop."

Follow-up questions

What is the difference between big-O and the worst case?

Big-O is a notation for an upper bound on growth; the worst case is a choice of input. You can give a big-O bound for the best, average or worst case, so say which one you mean.

Does space complexity include the recursion stack?

Yes, count it as extra memory. A recursive traversal holds one frame per active call, so its extra space grows with the depth of the recursion.

Why is appending to a list constant time if it sometimes copies everything?

It is constant in amortized cost: the course text shows that a resizing array handles any sequence of n operations in time proportional to n (Sedgewick and Wayne, accessed 2026-10-26), and the Python Wiki lists list append as amortized constant. In a doubling array (an illustrative growth rule), 100,000 appends copied 131,071 elements in total, about 1.31 per append.¹

What happens to the running time if the input doubles?

A linear algorithm takes about twice as long and a quadratic one about four times as long, as the doubling table above shows. A logarithmic one grows by a fixed small amount.

What if the input size is not given?

Ask for it. Constraints decide whether an O(n²) answer is acceptable, and asking shows you connect the bound to the problem. Clarifying constraints is a habit worth carrying into every round, from online assessments to the forward deployed and applied AI engineer rounds.

Sources

1. Algorithms, 4th edition, section 1.4: Analysis of Algorithms — Princeton University (Sedgewick and Wayne), accessed 2026-10-26, 26 Oct 2026
2. TimeComplexity - Python Wiki — Python Software Foundation, accessed 2026-10-26, 26 Oct 2026