9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ DFS is considered to […] of the tree not every graph traversed depth first is a tree. $\endgroup$ – greybeard Jan 7 '17 at 15:54
  • $\begingroup$ There's a difference between saying "this here DFS implementation has cost X" and "DFS can be implemented so that it has cost X". So seems to be argueing about different statements of the second kind, which need not be contradictory at all. (Note that there is no contradiction at all since $O(bm) \supset O(m)$, if $O(bm)$ is to mean anything at all.) $\endgroup$ – Raphael Jan 7 '17 at 16:14
  • $\begingroup$ @greybeard Can you tell me an example where a depth-first traversal on a graph would not result in a tree? $\endgroup$ – nbro Jan 7 '17 at 16:21
  • $\begingroup$ example where a depth-first traversal on a graph would not result in a tree without giving it too much thought: parsing. (Wait: what do you mean: result in a tree? The question is about Searching/traversing a graph.) $\endgroup$ – greybeard Jan 7 '17 at 16:28
  • $\begingroup$ @greybeard You started discussing, not me. What do you mean by "not every graph traversed depth first is a tree."? $\endgroup$ – nbro Jan 7 '17 at 16:35
2
$\begingroup$

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,

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ A pint in time keeps the doctor away. $\endgroup$ – greybeard Jan 7 '17 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.