---

Space and time complexity

The space and time complexity of DFS is

\[\mathcal{O}(bm) \qand \mathcal{O}(b^m)
\]

respectively,

where	\(b\)	is the branching factor and
	\(m\)	is the maximum search depth.