Discrete Mathsfor Engineers

7. Complexity

Branch & Bound is often much faster than brute force in practice, but that does not mean its worst-case complexity disappears.

To understand the method properly, we must distinguish between worst-case theoretical complexity and practical search reduction through pruning.

7.1 Worst-case complexity

In the worst case, Branch & Bound may still explore the entire search tree.

That means its time complexity can remain exponential:

where:

• b is the branching factor
• d is the depth of the search tree

In binary decision problems, this is often written as:

7.2 Why it is still useful

If the worst case is still exponential, why use Branch & Bound at all?

Because in many practical instances, the algorithm avoids exploring most of the tree.

Strong bounds and good incumbents can cut away huge portions of the search space before they are ever expanded.

7.3 The effect of pruning

The more nodes are pruned, the smaller the effective search tree becomes.

This means practical running time depends on:

• the quality of the bounding function,
• the speed of finding strong incumbents,
• and the node selection strategy.

So two Branch & Bound implementations for the same problem can have the same worst-case complexity but very different practical behavior.

7.4 Space complexity

Space complexity depends strongly on the node selection strategy.

• DFS: usually low memory, because only a path and a small frontier are kept
• BFS: can require very large memory, because many nodes at the same level remain stored
• Best-first: often requires substantial memory, since many live nodes may stay in the priority queue

In practice, memory can be as important as time when evaluating a Branch & Bound method.

7.5 Cost of computing bounds

Complexity is not determined only by how many nodes are visited.

Each node may also require nontrivial work to compute its bound.

So total running time depends on both:

1. the number of visited nodes,
2. and the cost per node.

This is why a stronger bound is not automatically better: it may reduce the tree, but increase the work done at each node.

7.6 Instance-dependent behavior

Branch & Bound is highly instance-dependent.

On some inputs, pruning may be extremely effective. On others, almost no pruning may happen at all.

This makes precise complexity prediction difficult.

7.7 Practical view of complexity

In practice, Branch & Bound is often evaluated by:

• number of expanded nodes,
• number of pruned nodes,
• memory usage,
• and total running time on representative instances.

This practical perspective is especially important in optimization engineering and solver design.

7.8 Summary

• Worst-case time remains exponential
• Pruning can drastically reduce search in practice
• Space depends strongly on the exploration strategy
• Total cost includes both visited nodes and bound computation
• Performance is highly instance-dependent