We read on Wikipedia > Iterative deepening depth-first search thatThe 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 solutiondef 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 NoneSo 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?
Space complexity of Iterative Deepening DFS
algorithm analysis;big o
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)?Check out http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.91.288 and http://intelligence.worldofcomputing.net/ai-search/depth-first-iterative-deepening.html