# Why the space complexity of depth-first search is O(bm)?

In "Artificial Intelligence: A Modern Approach", the authors say that the space complexity of depth-first search is proportional to O(bm), considering b as the branching factor and m the maximum depth of the graph. But it is not obvious why, for me.

The algorithm for searching graphs involves storing the explored nodes in the explored set, and the nodes open, but not explored yet, are stored in the border set.

Let us consider the following graph, with the start node in green and the end node (the goal) in red.

The solution is given by the red path.

But, in my perspective, in this scenario, in the worst case, the algorithm would try every path from the root to each leaf, and store all the nodes in the explored set.

Thus, if we consider this, the space complexity is, at least, proportional to $$O(b^m)$$.

Is there something wrong with this reasoning?

I'm including another image to represent better the searching process on a graph.

Best regards.

• To visit a node again, you have to visit the node's parent. If you're at the node's parent, you do need to mark off the node. But if not, you only need to mark off the parent. You can continue upwards: if you're not at the grandparent, you only have to mark off the grandparent. You end up only needing to mark off nodes adjacent to your path, which is $O(bm)$ in space. This works for any graph. Jan 13 at 12:07