Explain BFS space complexity.
When using the breadth-first search algorithm, is the space complexity O(bd), where b is the branching factor and d the length of the optimal path (assuming that there is indeed one)?
The BFS space complexity is O(bd) in the worst case, and it corresponds to the largest possible number of nodes that may be stored in the frontier at once, where the frontier is the set of nodes (or states) that you are currently considering for expansion. You can take a look at section 3.5 (page 74) of the book Artificial Intelligence: A Modern Approach (3rd edition, by Norvig and Russell) for more info about the time and space complexity of BFS.