Time Complexity and Space Complexity of DFS and BFS Algorithms

In this post, we will analyze the time and space complexity for Depth First Search and Breadth First Search algorithms …

Before looking into time and space complexity for Graph traversal algorithms such as Depth-First Search and Breadth-First Search algorithms, let’s understand what is time complexity and space complexity in general.

Time Complexity

• The time complexity of an algorithm describes how the algorithm’s runtime grows as the input size increases.
• It is denoted using big O notation, such as O(f(n)), where “f(n)” represents the function that defines the upper bound on the growth rate of the algorithm.
• For example, O(n) means the algorithm’s runtime grows linearly with the input size, O(n²) means the runtime grows quadratically, and O(log n) means the runtime grows logarithmically.

Space Complexity

• The space complexity of an algorithm describes how much additional space or memory the algorithm requires to solve a problem as the input size increases.
• It is also denoted using big O notation, such as O(f(n)), where “f(n)” represents the function that defines the upper bound on the space used by the algorithm.
• The space complexity considers both the auxiliary space (additional space used by the algorithm itself) and the input space (space required to store the input).
• Similar to time complexity, space complexity can have different notations like O(1) for constant space, O(n) for linear space, O(n²) for quadratic space, etc.

Depth First Search — Time Complexity

• In DFS, the time complexity is determined by the number of vertices (nodes) and edges in the graph.
• For each vertex, DFS visits all its adjacent vertices recursively.
• In the worst case, DFS may visit all vertices and edges in the graph.
• Therefore, the time complexity of DFS is O(V + E), where V represents the number of vertices and E represents the number of edges in the graph.

Depth First Search — Space Complexity

• The space complexity of DFS depends on the maximum depth of recursion.
• In the worst case, if the graph is a straight line or a long path, the DFS recursion can go as deep as the number of vertices.
• Therefore, the space complexity of DFS is O(V), where V represents the number of vertices in the graph.

Breadth First Search — Time Complexity

• In BFS, the time complexity is also determined by the number of vertices (nodes) and edges in the graph.
• BFS visits all the vertices at each level of the graph before moving to the next level.
• In the worst case (as we always talk about upper bound in Big O notation), BFS may visit all vertices and edges in the graph.
• Therefore, the time complexity of BFS is O(V + E), where V represents the number of vertices and E represents the number of edges in the graph.

Breadth First Search — Space Complexity

• The space complexity of BFS depends on the maximum number of vertices in the queue at any given time.
• In the worst case, if the graph is a complete graph, all vertices at each level will be stored in the queue.
• Therefore, the space complexity of BFS is O(V), where V represents the number of vertices in the graph.

In summary, the time complexity of both DFS and BFS is O(V + E), where V represents the number of vertices and E represents the number of edges in the graph. And, the space complexity of DFS and BFS is O(V), in the worst case.

If you’re gearing up for coding interviews, Handbook for Coding Interviews book is the perfect prep guide.

If you found this post useful, please follow me on Medium.