# Space complexity of Iterative Deepening DFS

We read on Wikipedia > Iterative deepening depth-first search that

The space complexity of IDDFS is O(bd), where b is the branching factor and d is the depth of shallowest goal.

Wikipedia also gives some decent pseudocode for IDDFS; I pythonified it:

``````def IDDFS(root, goal):
depth = 0
solution = None
while not solution:
solution = DLS(root, goal, depth)
depth = depth + 1
return solution

def DLS(node, goal, depth):
print("DLS: node=%d, goal=%d, depth=%d" % (node, goal, depth))
if depth >= 0:
if node == goal:
return node

for child in expand(node):
s = DLS(child, goal, depth-1)
if s:
return s

return None
``````

So my question is, how does the space complexity include the branching factor? Does that assume that `expand(node)` takes up `O(b)` space? What if `expand` uses a generator that only takes constant space? In that case, would the space complexity still be a function of the branching factor? Are there situations where it is even possible for `expand` to be a constant-space generator?

You're right. Wikipedia is wrong! Does anyone have the book referenced on Wikipedia to find out what they mean (maybe they're talking about an optimization of some sort)?

• It feels rather self-serving to accept an answer that says I am right and wikipedia is wrong, but oh well. ;) Thanks for the response to my santiy-check. Sep 16, 2011 at 0:08
• Am I wrong or is iterative deepening (in chess at least) used with a transposition table (cache of positions) so branches times depth is the cache size (space used)? Aug 7, 2012 at 3:32

I'm studying this as we speak, so let me try to answer this question (super late, I know) in hopes of understanding IDDFS more myself.

The O(bd) cost is derived from an implementation that uses a queue to store unexplored nodes, rather than recursion. If you think about it that way, then you can imagine that we expand the root node, and add b children to the queue (to be expanded later), then we pick one child (b-1 nodes left in the queue), expand it, and add its b children (b+(b-1) nodes in the queue), and repeat this process until we reach the goal node at depth d. At this point, we have expanded d nodes, yes? And each node leading up to the goal node has contributed b-1 nodes to the queue. Hence, we have O( (d-1)(b-1)) = O(bd).

Returning to your implementation, yes, I think you're right about the O(b) term being contained in the expand function, since expand will return b children and expand will be called d-1 times. If expand uses a generator that takes constant space, sure, I think that would reduce the cost to O(d), but I don't see how expand could do anything but scale with the size of b.

• I don't think it has to scale with b. Consider a graph problem where we are given a string, and at each point we can swap the positions of the first character in the string and any other character in the string. Then expand(node) can return an iterator with an internal state of an integer n. Every time we get the next value of expand(node), we increment n and return the string that comes about from swapping the 1st and nth character, and once n reaches the length of the string we stop. Here the internal storage of expand(node) only takes space proportional to the the log of the length of the Oct 7, 2014 at 22:08
• string, or ln(b). Oct 7, 2014 at 22:08
• What you described is a specific application which uses the nature of the problem to simplify the description of a node. You're right in that the space cost scales with log(b) (still scales with b, just not linearly). I (and I believe the question) was referring to a general instance of IDDFS that makes no assumptions about the problem statement, and only works on a generic tree with branching factor b and goal depth d. Oct 8, 2014 at 1:44