---

Space and time complexity

The space and time complexity of BFS is

\[\mathcal{O}(b^{d + 1}),
\]

where	\(b\)	is the branching factor and
	\(d\)	is the depth of the shallowest solution.