After reading about iterative deepening depth-first search on Wikipedia, I could understand that it just limits the depth upto which dfs can go in one iteration/call.However, I could not understand why it is said that it requires $O(b \times d)$ memory, where $b$ is fan-out of nodes i.e. children and $d$ is max-depth.Since it is just doing DFS multiple times, it should also only need $O(d)$ memory. Thinking more, I thought that may be the entire graph can not be put in memory and $O(b\times d)$ is the part of graph required to be kept in memory. But does that make DFS also have $O(b\times d)$ memory requirement ? But even this does not like a good argument, because since during traversal if we are fetching the new nodes from some storage, we can do so also with $O(d)$ memory.Also the Wikipedia page examples lead me to infer that it does not store visited[node_id] information about the nodes which stores whether node with id node_id is visited till now or not. This made me infer that graph is big.Edit: After thinking further i think that it is right about $O(b \times d)$, since it is iterative-dfs rather than recursive-dfs. In recursive-dfs we usually take memory used by function call stack for granted. In iterative-dfs, we can find right memory-requirements. Since, now we can not implicitly remember back-tracking, we have to put all children on the stack and hence if we are going to $d$ levels, we need $O(b\times d)$ memory.
Why Iterative-Deepening-DFS requires O(b*d) memory?
graphs;graph traversal
Well, one can say that $O(bd)$ is the bound for iterative-deepening depth-first search (DFID). It is not necessarily true that there is a mistake in Wikipedia. In general, every node is expanded and all its $b$ children are generated. Doing so allows for additional strategies, e.g., sorting them. Then a loop traverses all nodes and DFID is invoked recursively on each one. Thus, when a solution is found at depth $d$, $db$ nodes are stored in memory.However, in many cases you can do as you suggest and generate the children efficiently one at a time. In this particular case we usually say that DFID takes $O(d)$ (instead of $\Theta(d\log b)$): Instead of expanding all nodes you just take the first one and invoke DFID recursively over it. When the search resumes in this particular node we just take the next one. This sort of implementations works as Tom van der Zanden explained but there is no specific need to remember that we are located at the 2nd child or the 5th child. There are two reasons for this:Once the solution is found, the path to it is in the stack ---so you won't get lost, no need to remember which were the specific orderings of the children generated above your current state.A naive implementation might require remembering we considered the $n$-th child to generate the $(n+1)$-th child but some tricks can be used to avoid this specifically. Take for instance the $N$-puzzle. In this case, the descendants can be precomputed in a table (as Richard Korf did in his original implementation of IDA$^*$) and the children are just stored in an array of known length. Then $O(d)$ is feasible just by traversing this array. The same trick can be accomplished in other domains such as the $N$-pancake, the Rubik's cube, Topspin (where it is even easier!) and such ... As a matter of fact, Richard Korf (who originally devised the idea of DFID) describes the space complexity of DFID in page 100 in the following terms: since at any given time, it is performing a depth-first search, the space it uses is $O(d)$ Richard E. Korf. Depth-First Iterative-Deepening: An Optimal Admissible Tree Search. Artificial Intelligence Journal, 27(1). 1985. 99--121 This statement assumes that the considerations made above apply in your domain.However, it might be a good idea indeed to have a look at all descendants before starting to invoke DFID over them (and therefore incurring in a space complexity $O(bd)$), and Alexander Reinefeld considered a good number of ideas based on this observation. See the paper: Alexander Reinefeld. Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA$^*$. IJCAI 1993. 248--253. Finally, a similar idea (ie., generating only a specific node that satisfies a particular condition) has been tried also in the context of A$^*$. For more information see Meir Goldenberg, Ariel Felner, Nathan Sturtevant, Robert Holte, Jonathan Schaeffer. Optimal-Generation Variants of EPEA$^*$, Proceedings of the Fifth International Symposium on Combinatorial Search, (SoCS-2013), July 2013Cheers,