Backtracking Time & Space Complexity
The One Formula You Need
Every backtracking cost estimate comes from the shape of the search tree.
TIME ≈ (number of nodes in the tree) × (work done at each node)
+ (number of answers) × (cost to copy one answer)
SPACE ≈ depth of the tree (call stack + working path)
+ size of all stored answers (if you keep them)
So the job is always the same: estimate how many nodes the tree has, and how much work each node does.
Counting Nodes: Branching Factor and Depth
If every node has b children and the tree is d levels deep: level 0: 1 node level 1: b nodes level 2: b² nodes ... level d: b^d nodes ← the leaves dominate total = 1 + b + b² + ... + b^d = O(b^d) (for b ≥ 2) When the branching factor SHRINKS by one per level (orderings): level 0: 1 level 1: n level 2: n·(n-1) ... level n: n! ← again the leaves dominate total ≈ e · n! = O(n!)
Standard Bounds to Memorise
| Problem shape | Leaves (answers) | Work per answer | Total time | Aux. space |
|---|---|---|---|---|
| All subsets of n | 2ⁿ | O(n) copy | O(n · 2ⁿ) | O(n) |
| Choose k of n | C(n, k) | O(k) copy | O(k · C(n, k)) | O(k) |
| All orderings of n | n! | O(n) copy | O(n · n!) | O(n) |
| Fill d slots, m options each | mᵈ | O(d) copy | O(d · mᵈ) | O(d) |
| N-Queens (n×n) | ≤ n! | O(1) with attack sets | O(n!) | O(n) |
| Sudoku (e empty cells) | ≤ 9ᵉ | O(1) with bitmasks | O(9ᵉ) | O(e) |
| Word of length L on R×C grid | ≤ R·C·4·3^(L−1) | O(1) | O(R · C · 3ᴸ) | O(L) |
For the grid word search, the first letter can go 4 ways, but every later step has at most 3 — you never step straight back onto the cell you came from.
Measuring It: Counting Calls
Formulas are easier to trust when you watch the numbers. The program below counts recursive calls for three searches:
- ›Subsets (pick-next shape) — expect exactly 2ⁿ calls
- ›Orderings (used-set shape) — expect about e · n!
- ›N-Queens with and without pruning — see how much pruning saves
public class CountCalls {
static long calls;
static void subsets(int n, int start) {
calls++;
for (int j = start; j < n; j++) subsets(n, j + 1);
}
static void perms(int n, boolean[] used, int depth) {
calls++;
if (depth == n) return;
for (int j = 0; j < n; j++) {
if (!used[j]) {
used[j] = true;
perms(n, used, depth + 1);
used[j] = false;
}
}
}
static boolean attacked(int[] cols, int row, int c) {
for (int r = 0; r < row; r++)
if (cols[r] == c || Math.abs(cols[r] - c) == row - r) return true;
return false;
}
// Returns the number of valid boards found below this call
static int queens(int n, int row, int[] cols, boolean prune) {
calls++;
if (row == n) {
// Without pruning, the whole board is only checked here
for (int r = 1; r < n; r++)
if (attacked(cols, r, cols[r])) return 0;
return 1;
}
int found = 0;
for (int c = 0; c < n; c++) {
if (prune && attacked(cols, row, c)) continue; // pruned
cols[row] = c;
found += queens(n, row + 1, cols, prune);
}
return found;
}
public static void main(String[] args) {
System.out.println("n subset-calls ordering-calls");
for (int n = 1; n <= 6; n++) {
calls = 0; subsets(n, 0);
long s = calls;
calls = 0; perms(n, new boolean[n], 0);
System.out.println(String.format("%d %-12d %d", n, s, calls));
}
System.out.println();
System.out.println("n boards calls-no-pruning calls-with-pruning");
for (int n = 4; n <= 6; n++) {
calls = 0;
int boards = queens(n, 0, new int[n], false);
long raw = calls;
calls = 0;
queens(n, 0, new int[n], true);
System.out.println(String.format("%d %-6d %-16d %d", n, boards, raw, calls));
}
}
}Output:
n subset-calls ordering-calls
1 2 2
2 4 5
3 8 16
4 16 65
5 32 326
6 64 1957
n boards calls-no-pruning calls-with-pruning
4 2 341 17
5 10 3906 54
6 4 55987 153
Reading the Numbers
SUBSETS: calls double every time n grows by 1 → exactly 2^n. ✓
ORDERINGS: 1957 for n = 6, and 6! = 720.
1957 / 720 ≈ 2.72 ≈ e → total ≈ e · n! ✓
N-QUEENS: without pruning, every row tries every column:
1 + 6 + 6² + ... + 6⁶ = 55,987 calls for n = 6
with pruning: 153 calls — about 366× fewer,
for exactly the same 4 boards.
The worst-case formula for N-Queens is still quoted as O(n!), but the measured work is tiny compared to it. This is typical: pruning rarely changes the textbook bound, but it changes everything in practice.
Space Complexity in Detail
WHAT LIVES IN MEMORY DURING THE SEARCH: 1. Call stack one frame per level → O(depth) 2. Working path grows/shrinks by one → O(depth) 3. Helper state used[], attack sets, masks → O(n) usually 4. Stored answers every copy you keep → O(answers × size) AUXILIARY SPACE = 1 + 2 + 3 (what the algorithm itself needs) TOTAL SPACE = 1 + 2 + 3 + 4 (including the output) Example — all orderings of n = 10: auxiliary: ~10 frames + path of 10 + used[10] → O(n) output: 10! = 3,628,800 lists × 10 elements → O(n · n!)
When an interviewer asks for space complexity, state both: "O(n) auxiliary, O(n · n!) including the output".
Practical Size Limits
Exponential algorithms hit a wall quickly. As a rough guide for about 10⁸ simple operations per second:
GROWTH LARGEST n THAT RUNS IN ~1 SECOND ────── ──────────────────────────────── 2^n n ≈ 25–27 n · 2^n n ≈ 20–22 3^n n ≈ 16–17 n! n ≈ 10–11 n · n! n ≈ 9–10 If the problem says n ≤ 10 → orderings are fine If the problem says n ≤ 20 → subsets are fine, orderings are not If the problem says n ≤ 10^5 → backtracking is the wrong tool
Input limits are often the clearest hint about which technique the problem setter expects.
Common Mistakes
Forgetting the copy cost. Saying "subsets are O(2ⁿ)" is incomplete if you store each subset — copying adds a factor of n.
Counting only leaves. For trees whose branching factor is small (like 2), internal nodes are about as numerous as leaves. The asymptotic bound is unchanged, but measured timings can surprise you.
Assuming pruning improves the bound. Pruning almost always helps real inputs, but an adversarial input may defeat it. Quote the worst case, then mention the practical speed-up.
Ignoring per-node work. Checking a whole N-Queens board at every node costs O(n) or O(n²) per node. With attack sets or bitmasks, the same check is O(1), and the overall bound changes accordingly.
Interview Questions
Q: What is the time complexity of generating all subsets, and why can't it be improved?
O(n · 2ⁿ). There are 2ⁿ subsets and their combined length is n · 2ⁿ⁻¹, so merely writing out the answer takes that long. Any algorithm that lists every subset must spend at least that much time.
Q: Why is the space complexity of backtracking usually O(depth) and not O(number of nodes)?
Backtracking is a depth-first walk. At any moment only the nodes on the current root-to-node path are alive on the call stack; siblings are explored one at a time and their frames are released before the next sibling starts.
Q: How would you speed up a backtracking solution that is correct but too slow?
First, move validity checks earlier so bad branches are cut at a shallower depth. Second, make each check O(1) with sets, boolean arrays, or bitmasks. Third, order the options so promising or highly constrained choices come first. Finally, if the same sub-state repeats and only a count or best value is needed, add memoization.
Summary
- ›Time ≈ nodes × work per node + answers × copy cost.
- ›Branching factor b and depth d give O(bᵈ) nodes; shrinking branches give O(n!).
- ›Memorise the classics: subsets O(n · 2ⁿ), orderings O(n · n!), choose-k O(k · C(n, k)).
- ›Auxiliary space is O(depth); output space can be exponential — mention both.
- ›Pruning slashes real work (366× for 6-Queens above) even when the textbook bound stays the same.
Next, Subsets applies everything so far to the most fundamental backtracking pattern — including how to avoid duplicate subsets when the input repeats values.
A search has branching factor b at every level and depth d. What bounds the number of nodes?