Performance and Complexity

Search algorithms are compared on four criteria.

Completeness

If a solution exists, does the algorithm find one?

• BFS: complete (if branching factor is finite).
• DFS: not complete on infinite spaces (can wander down an infinite branch forever).
• A* with admissible heuristic: complete on finite spaces.

Optimality

When the algorithm finds a solution, is it the cheapest one?

• BFS: optimal only if all step costs are equal.
• Uniform-cost search (Dijkstra): optimal for any non-negative step costs.
• A* with admissible heuristic: optimal.
• DFS, greedy best-first: not optimal in general.

Time complexity

How long does it take? Usually expressed in terms of:

• $b$: branching factor
• $d$: depth of the shallowest solution
• $m$: maximum depth of the state space

For uninformed search the typical answer is $O(b^d)$ — exponential in solution depth. This is the central limitation of classical search and the reason heuristics matter.

Space complexity

How much memory?

• BFS: $O(b^d)$ — the frontier alone grows exponentially.
• DFS: $O(bm)$ — only stores the current path.
• A*: $O(b^d)$ — same problem as BFS.

Memory is usually the binding constraint in practical search problems. Algorithms like IDA* trade more time for less memory specifically to address this.

What these mean in practice

• $b = 2, d = 30$: $2^{30} \approx 10^9$ — feasible.
• $b = 10, d = 30$: $10^{30}$ — completely infeasible.
• $b = 10, d = 100$: heat death of the universe long before completion.

The lesson: depth dominates. Small reductions in effective branching factor (via heuristics, pruning, smart action ordering) translate into enormous speedups. This motivates everything in the next sections.