Answers.Body: <p>After spending some time on the problem, I concluded that it is due to the fact that we need to store the heuristic function evaluations for all nodes during the traversal. So, one might claim that it is the space complexity of the whole nodes which is simply <span class="math-container">$\mathcal{O}(b^m)$</span>. I hope this is correct.</p>
  
  <p>Also the one with having the space complexity of <span class="math-container">$\mathcal{O}(bm)$</span> is called recursive best-first search which is the one that is most similar to DFS implementation I descried in the question.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-24T14:41:48.313Z
Answers.Text: Have you any reference for this?
Answers.UserDisplayName: keramat
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-12T12:51:18.023Z
Answers.LastActivityDate: 2020-02-12T13:58:16.207Z
Answers.LastEditDate: 2020-02-12T13:58:16.207Z
Answers.UserDisplayName: iRestMyCaseYourHonor
Answers.Body: <p>I was struggling with the same question. This is what I came up with after thinking it through.</p>
  <p>With depth-first-search, you backtrack to a node that is a non-expanded child of your parent (or the parent of the parent when your parent has no more non-expanded children (and so on going up the tree)). So the space complexity is limited by your ancestors and the children of these ancestors. Which translates in m*b where m is the max path length (so max number of ancestors) and b is the branching factor (number of children per ancestor).</p>
  <p>With greedy search when you backtrack you can jump to any evaluated but unexpanded node, you passed going down on paths earlier. So the algorithm, when backtracking, can make pretty random jumps throughout the tree leaving lots of sibling nodes unexpanded. You will have to remember the value of the evaluation function for all these unexpanded nodes though because possibly they are next up when backtracking occurs. So in a theoretical very worst-case scenario that could mean that almost the whole tree needs to be remembered. Hence O(b^m).</p>
  <p>I know there are still gaps in the reasoning but intuitively this makes me understand it best.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-14T16:50:50.197Z
Answers.LastActivityDate: 2020-11-14T16:50:50.197Z
Answers.UserDisplayName: Thomas
Body: <p>I am reading through Artificial Intelligence: Modern Approach and it states that the space complexity of the GBFS (tree version) is <span class="math-container">$\mathcal{O}(b^m)$</span>.</p>
  
  <p>While I am reading, at some points, I found GBFS similar to DFS. It expands the whole branches and goes after one according to the heuristic function. It doesn't expand the rest like BFS. Perceiving this as similar to what depth-first search does, I understand that the worst time complexity is <span class="math-container">$\mathcal{O}(b^m)$</span>. But I don't understand the space complexity. </p>
  
  <p>Shouldn't it be the same as DFS, <span class="math-container">$\mathcal{O}(bm)$</span>, since it only will be expanding <span class="math-container">$b*m$</span> nodes during the search in one path?</p>
  
Tags: <search><time-complexity><computational-complexity><best-first-search><space-complexity>
Title: Why is the space-complexity of greedy best-first search is $\mathcal{O}(b^m)$?
UserDisplayName: iRestMyCaseYourHonor
ThreadText: # Why is the space-complexity of greedy best-first search is $\mathcal{O}(b^m)$?
  
  (Asked by: username_0 on 2020-02-11)
  
  I am reading through Artificial Intelligence: Modern Approach and it states that the space complexity of the GBFS (tree version) is $\mathcal{O}(b^m)$.
  
  While I am reading, at some points, I found GBFS similar to DFS. It expands the whole branches and goes after one according to the heuristic function. It doesn't expand the rest like BFS. Perceiving this as similar to what depth-first search does, I understand that the worst time complexity is $\mathcal{O}(b^m)$. But I don't understand the space complexity.
  
  Shouldn't it be the same as DFS, $\mathcal{O}(bm)$, since it only will be expanding $b\*m$ nodes during the search in one path?
  
  **Tags:** search, time-complexity, computational-complexity, best-first-search, space-complexity
  
  ---
  
  ## 2 answers
  
  ### Answer by username_0 on 2020-02-12. Score: 1 | Accepted answer
  
  After spending some time on the problem, I concluded that it is due to the fact that we need to store the heuristic function evaluations for all nodes during the traversal. So, one might claim that it is the space complexity of the whole nodes which is simply $\mathcal{O}(b^m)$. I hope this is correct.
  
  Also the one with having the space complexity of $\mathcal{O}(bm)$ is called recursive best-first search which is the one that is most similar to DFS implementation I descried in the question.
  
  > **Comments:**
  > **username_1**: Have you any reference for this?  
  
  ---
  
  ### Answer by username_2 on 2020-11-14. Score: 1
  
  I was struggling with the same question. This is what I came up with after thinking it through.
  
  With depth-first-search, you backtrack to a node that is a non-expanded child of your parent (or the parent of the parent when your parent has no more non-expanded children (and so on going up the tree)). So the space complexity is limited by your ancestors and the children of these ancestors. Which translates in m\*b where m is the max path length (so max number of ancestors) and b is the branching factor (number of children per ancestor).
  
  With greedy search when you backtrack you can jump to any evaluated but unexpanded node, you passed going down on paths earlier. So the algorithm, when backtracking, can make pretty random jumps throughout the tree leaving lots of sibling nodes unexpanded. You will have to remember the value of the evaluation function for all these unexpanded nodes though because possibly they are next up when backtracking occurs. So in a theoretical very worst-case scenario that could mean that almost the whole tree needs to be remembered. Hence O(b^m).
  
  I know there are still gaps in the reasoning but intuitively this makes me understand it best.
  
  
  ---
  
  