# What is the space complexity of breadth-first search?

When using the breadth-first search algorithm, is the space complexity $$O(b^d)$$, where $$b$$ is the branching factor and $$d$$ the length of the optimal path (assuming that there is indeed one)?

The space complexity of the breadth-first search algorithm is $$O(b^d$$) 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.