Home / Computer science / Depth-first search (DFS)
Computational complexity
The space and time complexity of DFS is
\[\mathcal{O}(bm) \qand \mathcal{O}(b^m)\]
respectively 1,
| where | \(b\) | is the branching factor and |
| \(m\) | is the maximum search depth. |
Footnotes:
1
In practice, often improved backtracking.