Discrete Mathsfor Engineers

7. Complexity

Backtracking is powerful, but it is also expensive.

Its running time depends on how many nodes of the search tree are actually explored.

In the worst case, this number grows exponentially.

7.1 Complexity Comes from the Search Tree

The complexity of backtracking is determined by the size of the search tree.

Each node represents a partial solution, and the algorithm may need to visit many such nodes.

Time complexity ≈ number of explored nodes.

7.2 Branching Factor

Let b be the branching factor, that is, the maximum number of children a node may have.

If each decision offers many choices, the tree expands very quickly.

Larger branching factor usually means larger running time.

7.3 Depth of the Tree

Let d be the maximum depth of the search tree.

In many problems, depth corresponds to the number of decision variables.

The deeper the tree, the more possible paths the algorithm may need to explore.

7.4 Worst-Case Time Complexity

If each node has up to b children and the tree has depth d, then the number of nodes may be on the order of:

This is the standard worst-case complexity of backtracking.

7.5 Examples

Different problems lead to different values of b and d.

• Subset generation: b = 2, d = n → O(2ⁿ)
• Permutation generation: roughly O(n!)
• N-Queens: exponential in the worst case
• Hamiltonian Path: exponential in the worst case

So even though the generic template is the same, the concrete cost depends strongly on the problem.

7.6 Space Complexity

Backtracking usually uses much less memory than breadth-first methods.

Since it explores one path at a time, the main memory cost comes from the recursion stack and the current partial solution.

More precisely, space is proportional to the maximum recursion depth, plus the state representation.

7.7 The Effect of Pruning

In theory, pruning does not change the worst-case class: backtracking often remains exponential.

But in practice, pruning can reduce the number of explored nodes dramatically.

• Worst-case complexity may stay exponential
• Observed runtime may improve enormously

7.8 Main Takeaway

Backtracking is expensive because it explores a combinatorial search tree.

Its cost is mainly controlled by:

• branching factor
• depth
• quality of pruning

This is why problem modeling and constraint design are just as important as the recursive code itself.