How to Analyze Backtracking Time Complexity: A Step-by-Step Guide

You nail the backtracking solution. The code runs. The interviewer asks for time complexity, and you say "O(n!)" because that's what you half-remembered from some blog post at 2am. The interviewer nods slowly. You're not wrong, exactly. You're just incomplete, and incomplete sounds worse than uncertain.

Miss either cost and your analysis is wrong.

The Two Costs Nobody Explains Together

Every backtracking algorithm has two distinct cost components:

1. Traversal cost: the work done at every node in the recursion tree (choosing, recursing, and undoing)
2. Copy cost: the work done at each leaf when you record a valid result

Most explanations say "there are n! permutations so the answer is O(n!)." That's like quoting a printer at $50 because that's what the hardware costs, ignoring the $300 in ink cartridges. The real answer for permutations is O(n * n!).

The general formula:

Total time = (nodes in recursion tree) × (work per node)
           + (leaves) × (work per leaf)

For most backtracking problems, copy cost at the leaves dominates. When both terms are the same order, keep one. The diagram below shows exactly where each cost lands.

Subsets copy at every node. Permutations copy only at leaves. The formula changes accordingly.

Count the Nodes Before You Write a Formula

Draw the recursion tree before you write anything. At each level, ask:

• How many choices are available at this node?
• Does the branching factor stay constant, or shrink?
• How deep can the tree go?

Total nodes in a tree with constant branching factor b and depth d is O(b^d). If the branching factor shrinks (like permutations: pick from n, then n-1, then n-2), multiply: n × (n-1) × (n-2) × ... = n!.

Three canonical examples follow.

Subsets: O(n * 2^n)

def subsets(nums):
    result = []

    def backtrack(start, current):
        result.append(current[:])  # copy cost at every node
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()

    backtrack(0, [])
    return result

Each element is either in or out. For n elements, that gives 2^n subsets. Total nodes across all levels is 2^(n+1) - 1, so O(2^n). Note that result.append(current[:]) runs at the top of the function, before the loop. This means every single node in the tree pays the copy cost, not just the leaves.

At each node, you copy a subset of average length n/2. Total copy cost: O(2^n × n/2) = O(n × 2^n).

The traversal cost (append and pop) is O(1) per node, so O(2^n) total. Dominated.

Final: O(n × 2^n) time. For n=20, roughly 20 million operations. Fine. For n=30, 30 billion. This is why backtracking problems always cap n in the low twenties. If you see n ≤ 15 on a whiteboard problem, that's the interviewer quietly signaling that backtracking is acceptable.

Permutations: O(n * n!)

def permute(nums):
    result = []

    def backtrack(current, remaining):
        if not remaining:
            result.append(current[:])  # O(n) copy
            return
        for num in remaining:
            current.append(num)
            backtrack(current, remaining - {num})
            current.pop()

    backtrack([], set(nums))
    return result

At the first level, n choices. Second, n-1. Third, n-2. Number of leaves = n!. Total internal nodes sum to roughly e × n!, still O(n!).

At each leaf, you copy a length-n permutation: O(n) work.

Total copy cost: O(n × n!).

The traversal cost is also O(n × n!), since there are O(n!) nodes each doing O(n) work in the loop. Same order, doesn't change the result.

Final: O(n × n!) time. For n=12, nearly 2 billion operations. For n=15, you'd be waiting longer than your last code review. You won't see n > 10 in any real permutation problem. If you do, your interviewer either made a typo or is testing whether you'll push back.

Me running permute(range(12)) just to test it.

Combinations: O(k * C(n, k))

def combine(n, k):
    result = []

    def backtrack(start, current):
        if len(current) == k:
            result.append(current[:])  # O(k) copy
            return
        for i in range(start, n + 1):
            current.append(i)
            backtrack(i + 1, current)
            current.pop()

    backtrack(1, [])
    return result

The number of leaves is C(n, k). Each combination has exactly k elements, so copy cost per leaf is O(k).

Total copy cost: O(k × C(n, k)).

You can bound the traversal cost by summing C(n, 0) + C(n, 1) + ... + C(n, k-1), which is at most 2^n. The dominant term stays O(k × C(n, k)).

For k = n/2, C(n, k) hits its maximum and grows as 2^n / sqrt(n) by Stirling's approximation. Combinations at the midpoint behave like subsets.

Final: O(k × C(n, k)) time.

Pruning Does Not Fix Your Worst Case (Sorry)

Pruning cuts branches early when a partial solution can't lead anywhere valid. In Sudoku or N-Queens, it eliminates enormous chunks of the tree. The practical speedups are real and sometimes dramatic.

People get overconfident here. Pruning reduces the constant factor and average-case cost, but does not change worst-case asymptotic complexity.

In the best case, pruning can reduce a 2^n algorithm to nearly O(n^2). The worst case remains 2^n. In an interview, give both: "Worst case is O(n × 2^n) without pruning fully kicking in, but pruning typically makes it much faster in practice."

You after adding pruning: "Got it, won't visit impossible branches again." Worst-case complexity:

Don't say "pruning makes it polynomial." That almost never holds and will get you a frown.

Space Is Stack Depth, Not Total Nodes

This one gets people consistently.

Space complexity has two independent components:

Recursion stack depth: always O(d), where d is the maximum depth of the recursion tree. For subsets and permutations with n elements, this is O(n). You're doing DFS, so only one root-to-leaf path is ever live on the stack.

Output space: O(number of solutions × size per solution). For subsets: O(n × 2^n). For permutations: O(n × n!).

The common mistake is confusing O(2^n) total nodes visited with O(2^n) space. You visit 2^n nodes but never have more than O(n) active simultaneously. Think of it like exploring a city: you walk every street, but you're only standing on one street at a time.

If the interviewer asks for space excluding output, the answer is almost always O(n).

Analyzing Backtracking in Interviews

When asked for complexity on a backtracking solution, walk through this sequence out loud:

1. Count the leaves. Subsets: 2^n. Permutations: n!. Combinations: C(n, k).
2. Find the copy cost per leaf. Usually O(n) or O(k).
3. Multiply. That's your dominant term for most problems.
4. Check traversal cost. For most problems it's the same order, so it doesn't change the answer.
5. State space explicitly. O(n) stack depth, O(output) if asked.

Walking through these steps out loud is significantly more credible than pattern-matching "looks like n!, must be O(n!)." Interviewers aren't just checking if you landed on the right number. They're watching whether you have a framework or got lucky.

Voice practice matters here because explaining complexity under pressure is a different skill than understanding it at a desk. If you want to stress-test your reasoning in a realistic interview format, SpaceComplexity runs AI-powered mock interviews that score communication and analysis together, not just the final answer.

For full derivations, see backtracking time complexity. If you're still building intuition for what backtracking does, what is backtracking is the right starting point. For the full recursion complexity toolkit including Master Theorem and recurrence relations, recursion time complexity covers it end to end.

Further Reading

• Backtracking, Wikipedia
• Introduction to Backtracking, GeeksforGeeks
• Backtracking to Find All Subsets, GeeksforGeeks
• LeetCode 46: Permutations
• LeetCode 78: Subsets