DFS Time Complexity (Big-O)
Depth-first search runs in O(V + E) time and O(V) space, exploring a graph by recursing as deep as possible before backtracking. It underlies topological sort and strongly-connected-component algorithms.
Open the interactive DevRef Hub tool →Key facts
| Time | O(V + E) |
|---|---|
| Space | O(V) |
| Strategy | Go deep, then backtrack |
| Uses | Topological sort, SCC |
Frequently asked questions
What is the time complexity of DFS?
O(V + E), where V is vertices and E is edges.
BFS vs DFS?
Both are O(V + E); BFS explores by layers, DFS goes deep first.
Related pages
Big-O of DFS is part of DevRef Hub on GOAT Lab — a free reference you can use without signing up, and it works offline. Open the tool above for any custom value.
Part of GOAT Lab — 26 free, browser-based science, engineering and developer tools. No sign-up.