Why is DFS considered to have $O(bm)$ space complexity?

Question

According to these notes, DFS is considered to have $O(bm)$ space complexity, where $b$ is the branching factor of the tree and $m$ is the maximum length of any path in the state space.

The same is said in this Wikibook page on Uninformed Search.

Now the "infobox" of the Wikipedia article on DFS presents the following for the space complexity of the algorithm:

$O(|V|)$, if entire graph is traversed without repetition, $O($longest path length searched$)$ for implicit graphs without elimination of duplicate nodes

which is more similar to what I thought was the space complexity of DFS, i.e., $O(m)$, where $m$ is the maximum length reached by the algorithm.

Why do I think this is the case?

Well, basically we don't need to store any other nodes than the nodes of the path we're currently looking at, so there's no point of multiplying by $b$ in the analysis provided both by the Wikibook and the notes I'm referred you to.

Moreover, according to this paper on IDA* by Richard Korf, the space complexity of DFS is $O(d)$, where $d$ is considered the "depth cutoff".

So, what's the correct space complexity of DFS?

I think it may depend on the implementation, so I would appreciate an explanation of the space complexity for the different known implementations.

Answer 1

It depends on what exactly you call DFS. Consider for example the algorithm DFS-iterative described in Wikipedia, and suppose that you run it on a tree so that you don't have to keep track of which nodes you have already visited. Suppose that you run it on a complete $b$-ary tree of depth $m$. We can identify nodes in their tree with words over $[b]$ of length at most $m$. The algorithm operates as follows:

1. Start at the root. Push $1,2,\ldots,b$ to the stack (in reverse order).

2. Pop $1$, and push $11,12,\ldots,1b$ to the stack.

3. Pop $11$, and push $111,112,\ldots,11b$ to the stack.

4. $\ldots$

5. Pop $1^{m-1}$, and push $1^m,1^{m-1}2,\ldots,1^{m-1}b$ to the stack.

At this point, the stack contains

$$ 1^m,1^{m-1}2,\ldots,1^{m-1}b,\ldots,112,\ldots,11b,12,\ldots,1b,2,\ldots,b, $$

for a total of $(b-1)m + 1$ nodes. You can check that this is the pint in time in which the size of the stack is maximized.

Answer 2

There are two points here to make:

1. In case you introduce into the stack all the descendants of the current node, then effectively, the space complexity is $O(bd)$ where $b$ is the branching factor and $d$ is the maximum length. Yuval Filmus' reply refers to this case indeed. However, note that in general $d$ is much much larger than $b$. Moreover, in many domains, such as the sliding-tile puzzle, $b$ is upper bounded by a constant (in that specific case, 4) and hence we can safely say that DFS has a space complexity which is $O(d)$.

2. Admittedly, however, this is not always the case. For example, in the Pancake puzzle, the branching factor grows with the length of the optimal solution and they both have similar values. Still, the space complexity is $O(d)$. To see this just simply tweak the expansion procedure of any node: Instead of inserting all descendants of the current node (as suggested by Yuval Filmus) insert them in order. You first generate the first descendant and immediately after you proceed in depth-first order ---as a matter of fact, you do not need all the other descendants at this point. In case you ever backtrack to this node, then its descendant has been removed from the stack. Next, generate the second descendant and proceed in depth-first order again. In case you backtrack to this node, then generate the third and so on until there are no more descendants. Proceeding this way you will only have $d$ nodes in your stack, no matter of the branching factor, $b$.

Summarizing, I would never say that DFS has a space complexity which is $O(bd)$ and, instead, I claim its space complexity is $O(d)$.

Hope this helps,