How to Estimate Time Complexity: The Interview Guide

The problem is solved. Your code runs. You even handled the edge cases. Then the interviewer says "what's the time complexity?" and your brain quietly submits its resignation.

Not gradually. All at once. You stare at code you just wrote and cannot explain how fast it is. This happens to people who aced the problem, people who read CLRS cover to cover, people who definitely know what Big-O means. It happens because knowing complexity and producing it on demand under pressure are different skills.

How to estimate time complexity is a repeatable skill: count loops, watch for halving, draw the recursion tree when recursion appears. That covers 90% of what you'll face. The rest of this guide makes each step concrete.

Interviewer asks for time complexity; candidate panics and guesses O(n!)

"It's... definitely polynomial. Probably."

Three Questions to Answer Before You Open Your Mouth

Every complexity analysis answers the same three things.

What is n? (What input grows?)
How many times does the dominant operation execute, relative to n?
Is there recursion? (That needs separate treatment.)

Most people skip question 1 and get burned by it. "What is n?" sounds trivial until you're looking at a graph algorithm where n could mean vertices, edges, or both. BFS is O(V + E), and if you just say O(n) you've hand-waved away what might be the most interesting part of the answer. The interviewer noticed.

For iterative code, questions 1 and 2 are usually sufficient. Recursion is where candidates lose points, because the complexity hides in the shape of the call tree, not the visible loop structure.

Loops Tell You Everything in Iterative Code

One loop over n elements: O(n). That's the baseline.

for i in range(n):
    process(arr[i])  # O(1) per element

Nesting multiplies. Sequential loops add.

for i in range(n):
    for j in range(n):   # O(n²), nested
        process(i, j)

for i in range(n):       # O(n + m), sequential
    process_a(i)
for j in range(m):
    process_b(j)

The trap that catches people: the inner loop doesn't always run n times.

for i in range(n):
    for j in range(i):   # runs 0, 1, 2, ..., n-1 times
        process(i, j)

That inner loop runs 0 times, then 1, then 2, up to n-1. Sum is n(n-1)/2. Still O(n²), but you proved it instead of memorizing it. That matters more in an interview than you'd think. An interviewer who hears "O(n²)" and asks a follow-up wants justification, not just the label.

When the inner loop bound depends on the outer variable in less obvious ways, Nested Loop Time Complexity works through the edge cases.

When You See Halving, You See O(log n)

Any algorithm that cuts its remaining work in half at each step runs in O(log n). This is where logarithms come from: a problem that halves k times reaches size 1 when 2^k = n, so k = log₂(n).

Binary search is the clearest example. Each comparison eliminates half the array. After k comparisons you've reduced n items to 1, so k = log n. If you've ever wondered why binary search stays fast on huge arrays, this is it: a billion-item sorted array takes about 30 comparisons.

The pattern shows up wherever work shrinks geometrically: balanced BST operations, exponentiation by squaring, finding a position in a sorted structure.

O(n log n) is just the combination. Process n elements, each taking O(log n) work. Or do O(n) work at each of log n levels. Both describe merge sort. O(n log n) also happens to be the floor for comparison-based sorting, by an information-theoretic argument. Knowing that floor matters: it tells you when to stop trying to optimize. You can't sort faster than O(n log n) with comparisons. That's physics, not a skill issue.

Recursion: Draw the Tree

Iterative code is transparent. Recursive code hides its complexity in the shape of the call tree. Looking at a recursive function and trying to intuit the runtime without drawing anything is how you end up confidently saying the wrong number.

Total work = work per node times number of nodes, summed across the tree. For uniform-cost nodes, just multiply.

Three shapes cover most interview recursion:

Linear chain. T(n) = T(n-1) + O(1). Each call shrinks n by 1 and does constant work. Chain of n calls: O(n) time, O(n) stack space. Factorial, linked list traversal.

Two-way halving. T(n) = 2T(n/2) + O(n). log n levels, each doing O(n) total work. Result: O(n log n). Merge sort.

Uncached branching. T(n) = 2T(n-1) + O(1). Each call spawns two more, and n only shrinks by 1. At level k you have 2^k nodes. With n levels: 2^n nodes doing O(1) work each. Result: O(2^n). This is naive Fibonacci. It computes fib(2) something like 2^(n-2) times. Every. Single. Time.

Diagram showing the three recursion tree shapes: linear chain O(n), two-way halving O(n log n), and uncached branching O(2^n)

When the recurrence doesn't fit one of these shapes, the Master Theorem handles the general case T(n) = aT(n/b) + f(n). Recursion Time Complexity traces merge sort and Fibonacci through the full derivation.

Memoization Collapses the Exponential

Uncached recursion recomputes the same subproblems over and over. The tree explodes because it keeps solving things it already solved. Cache the results and each unique subproblem gets computed exactly once. The exponential tree collapses into a DAG, and so does the runtime.

Time = (number of unique states) times (work per state, not counting recursive calls).

Fibonacci without memoization: O(2^n). With memoization: n unique values, O(1) work each. O(n). That's not a micro-optimization. At n=50, you're going from roughly a quadrillion operations to fifty.

Coin change with target T and k denominations: T times k unique states, O(k) work per state. Result: O(T times k). 0/1 knapsack with n items and capacity W: n times W unique states, O(1) per state. Result: O(nW).

The formula is identical every time. Identify the state parameters, count the distinct states, multiply by the work per state. No memorizing per-algorithm formulas.

Memoization is an annoying term meme

The name is confusing. The technique is just "remember what you already computed."

For how this applies to grid traversal, LCS, and string problems, see Memoization Time Complexity.

Space Complexity Lives in the Call Stack

Iterative code: space equals what you explicitly allocate. A hash map with n keys is O(n). Two pointers is O(1). Most candidates handle this fine.

Recursive code has a hidden cost that a surprising number of people forget to mention. The call stack holds one frame per active call, and maximum simultaneous frames equals the depth of the tree, not the total node count.

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

O(n) time, O(n) space. At peak depth, n frames sit on the stack simultaneously. Easy to overlook because the recursion feels like it "goes away" after each call returns. It does go away, but not before it piles up.

Binary search done recursively: depth is log n, so O(log n) stack space. Merge sort: O(log n) stack frames from the recursion depth, but O(n) for the temporary arrays during merging. The O(n) dominates.

At Google and Meta, space complexity is scored as a separate dimension. Finishing your time analysis and stopping there leaves a scored box empty. Say both. Every time.

Commit This Table

Code structure	Time	Space
Single loop	O(n)	O(1)
k nested loops	O(n^k)	O(1)
Binary search (iterative)	O(log n)	O(1)
Binary search (recursive)	O(log n)	O(log n) stack
Linear recursion	O(n)	O(n) stack
Merge sort style recursion	O(n log n)	O(n)
Uncached branching recursion	O(2^n)	O(n) stack
Memoized DP	O(states)	O(states)
Backtracking, subsets	O(n · 2^n)	O(n)
Backtracking, permutations	O(n · n!)	O(n)

The space column is where most interview answers are incomplete. The backtracking rows trip people up because the copy cost per leaf is easy to overlook. Backtracking Time Complexity has the binomial theorem derivation that proves the subset row.

Three Examples, Read Cold

Two sum with a hash map:

seen = {}
for i, num in enumerate(nums):
    if target - num in seen:
        return [seen[target - num], i]
    seen[num] = i

Single loop, O(1) hash map operations: O(n) time. Hash map stores up to n entries: O(n) space.

Cycle detection with two pointers:

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        return True

Two pointers, at most n iterations before meeting or exhausting the list: O(n) time. No extra memory: O(1) space.

Generate all subsets:

result = [[]]
for num in nums:
    result += [curr + [num] for curr in result]

After n iterations there are 2^n subsets. At step i, the inner comprehension copies 2^(i-1) lists of length i. The total work sums to O(n · 2^n), not O(2^n). Counting subsets misses the copy cost. That difference is the answer most candidates don't give.

What to Say After You Get the Answer

The complexity number is half the score. The other half is how you communicate it.

A complete answer has three parts: the class, the justification, and space stated separately.

"O(n log n). The outer loop runs n times and each heap insertion runs O(log n). Space is O(n) for the heap."

If you're uncertain, reason aloud. Walking through the logic, even if you adjust mid-sentence, shows the interviewer how you think. Silence shows nothing, and saying nothing is a much worse outcome than saying something partially wrong that you then correct.

One mistake that fails candidates who got the right answer: not flagging worst case versus average case. Quicksort is O(n log n) average but O(n²) worst case on a sorted array. Hash map operations are O(1) average, O(n) worst under adversarial collision. Always say which one you're giving, because the follow-up might require you to defend it.

The follow-ups are harder. "Can you do better?" requires knowing theoretical lower bounds. Comparison-based sorting can't beat O(n log n). Hash table lookup can't beat O(1) with static keys. Knowing the floor tells you when to stop optimizing rather than chasing an improvement that physically cannot exist.

"What's the space-time tradeoff here?" requires articulating the exchange explicitly. Memoization converts O(2^n) time to O(n) time at the cost of O(n) space. A hash map trades O(n) space for O(1) lookup instead of O(log n). These are real decisions, not trivia. Interviewers asking this question want to know you understand what you're giving up.

Defending your analysis out loud, in real time, under follow-up pressure is a different skill from reading complexity off a page. SpaceComplexity runs voice-based mock interviews where those follow-ups come at you live. Try a session and find out where your analysis actually breaks.