# What is the space complexity of bidirectional search?

Is the space complexity of the bidirectional search, where the breadth-first search is used for both the forward and backward search, $$O(b^{d/2})$$, where $$b$$ is the branching factor and $$d$$ the length of the optimal path (assuming that there is indeed one)?

$$O(2b^{d/2}) = O(b^{d/2}).$$
The intuition behind this result is that (as opposed to e.g. uniform-cost search or breadth-first search, which have space (and time) complexity of $$O(b^{d})$$) is that the forward and backward searches only have to go half way, so you will not eventually need to expand all $$b^{d}$$ leaves, but only half of them.