Why is DFS considered to have \$O(bm)\$ space complexity? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T07:27:32Z https://cs.stackexchange.com/feeds/question/68359 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/68359 9 Why is DFS considered to have \$O(bm)\$ space complexity? nbro https://cs.stackexchange.com/users/20691 2017-01-07T00:46:18Z 2017-01-08T17:48:19Z <p>According to <a href="https://github.com/vivin/cse598/blob/master/mt1/AI_midterm_notes.md" rel="noreferrer">these notes</a>, <em>DFS</em> 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. </p> <p>The same is said in this <a href="https://en.wikibooks.org/w/index.php?title=Artificial_Intelligence/Definition&amp;stable=0#Uninformed_Search" rel="noreferrer">Wikibook page on <em>Uninformed Search</em></a>.</p> <p>Now the "infobox" of the <a href="https://en.wikipedia.org/wiki/Depth-first_search" rel="noreferrer">Wikipedia article on DFS</a> presents the following for the space complexity of the algorithm:</p> <blockquote> <p>\$O(|V|)\$, if entire graph is traversed without repetition, \$O(\$longest path length searched\$)\$ for implicit graphs without elimination of duplicate nodes</p> </blockquote> <p>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. </p> <p><em>Why do I think this is the case?</em></p> <p>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.</p> <p>Moreover, according to this <a href="https://cse.sc.edu/~mgv/csce580f09/gradPres/korf_IDAStar_1985.pdf" rel="noreferrer">paper on <em>IDA*</em></a> by <em>Richard Korf</em>, the space complexity of DFS is \$O(d)\$, where \$d\$ is considered the "depth cutoff".</p> <p>So, what's the correct space complexity of DFS? </p> <p>I think it may depend on the implementation, so I would appreciate an explanation of the space complexity for the different known implementations.</p> https://cs.stackexchange.com/questions/68359/-/68371#68371 6 Answer by Yuval Filmus for Why is DFS considered to have \$O(bm)\$ space complexity? Yuval Filmus https://cs.stackexchange.com/users/683 2017-01-07T07:48:05Z 2017-01-07T07:48:05Z <p>It depends on what exactly you call DFS. Consider for example the algorithm DFS-iterative described in <a href="https://en.wikipedia.org/wiki/Depth-first_search" rel="noreferrer">Wikipedia</a>, 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:</p> <ol> <li><p>Start at the root. Push \$1,2,\ldots,b\$ to the stack (in reverse order).</p></li> <li><p>Pop \$1\$, and push \$11,12,\ldots,1b\$ to the stack.</p></li> <li><p>Pop \$11\$, and push \$111,112,\ldots,11b\$ to the stack.</p></li> <li><p>\$\ldots\$</p></li> <li><p>Pop \$1^{m-1}\$, and push \$1^m,1^{m-1}2,\ldots,1^{m-1}b\$ to the stack.</p></li> </ol> <p>At this point, the stack contains</p> <p>\$\$ 1^m,1^{m-1}2,\ldots,1^{m-1}b,\ldots,112,\ldots,11b,12,\ldots,1b,2,\ldots,b, \$\$</p> <p>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.</p> https://cs.stackexchange.com/questions/68359/-/68421#68421 2 Answer by Carlos Linares López for Why is DFS considered to have \$O(bm)\$ space complexity? Carlos Linares López https://cs.stackexchange.com/users/1337 2017-01-08T17:06:27Z 2017-01-08T17:48:19Z <p>There are two points here to make:</p> <ol> <li><p>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)\$. </p></li> <li><p>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 <em>immediately after</em> you proceed in depth-first order ---as a matter of fact, <em>you do not need all the other descendants at this point</em>. 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\$.</p></li> </ol> <p>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)\$.</p> <p>Hope this helps,</p>