patternMinor
Why is DFS considered to have $O(bm)$ space complexity?
Viewed 0 times
whyspacedfsconsideredcomplexityhave
Problem
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.
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.
Solution
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:
-
Start at the root. Push $1,2,\ldots,b$ to the stack (in reverse order).
-
Pop $1$, and push $11,12,\ldots,1b$ to the stack.
-
Pop $11$, and push $111,112,\ldots,11b$ to the stack.
-
$\ldots$
-
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.
-
Start at the root. Push $1,2,\ldots,b$ to the stack (in reverse order).
-
Pop $1$, and push $11,12,\ldots,1b$ to the stack.
-
Pop $11$, and push $111,112,\ldots,11b$ to the stack.
-
$\ldots$
-
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.
Context
StackExchange Computer Science Q#68359, answer score: 7
Revisions (0)
No revisions yet.