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?


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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.