Time and Space Complexity of Depth First Search

When we use an algorithm like Depth First Search (DFS) to explore a graph, it’s important to understand how efficient it is. We measure this efficiency using two main concepts: time complexity (which predicts how long it takes to run) and space complexity (which predicts how much memory it uses). This knowledge helps you predict how your algorithm will perform with different input sizes and whether it’s suitable for your specific application.

Tip

To fully grasp the concepts discussed in this article, it’s recommended to first familiarize yourself with the fundamentals of DFS. You can gain a solid understanding by exploring these resources: Introduction to Depth First Search In a Graph, How Depth First Search (DFS) Works: Step-by-Step Explanation, and DFS Algorithm: Pseudocode and Explanation.

Time Complexity of DFS

Time complexity tells us how the running time of an algorithm grows as the input size increases. For graphs, the input size is usually described by:

  • V: The number of vertices (nodes or points) in the graph.
  • E: The number of edges (connections or lines) between the vertices.

The time taken by DFS depends heavily on how the graph is represented:

  1. Using an Adjacency List:

    • An adjacency list represents a graph as an array (or map) where each index corresponds to a vertex, and the value at that index is a list of its neighbors. You can learn more about Adjacency List here: Representing Graph using Adjacency List.
    • In DFS, we need to visit each vertex at most once. This takes O(V) time in total.
    • We also need to explore the edges connected to each vertex. When using an adjacency list, we only look at the outgoing edges for each vertex. Over the course of the entire DFS traversal, each edge (u, v) is examined exactly once when we explore from vertex u. So, examining all edges takes O(E) time in total.
    • Combining these, the total time complexity for DFS using an adjacency list is O(V + E). This is very efficient, especially for sparse graphs (graphs with relatively few edges).

  2. Using an Adjacency Matrix:

    • An adjacency matrix represents a graph as a V x V grid where matrix[i][j] = 1 if there’s an edge from vertex i to vertex j, and 0 otherwise. You can learn more about Adjacency Matrix here: Representing Graph using Adjacency Matrix.
    • Visiting each vertex still conceptually takes O(V) time.
    • However, to find the neighbors of a vertex u, we need to scan the entire row corresponding to u in the matrix. This takes O(V) time for each vertex.
    • Since we do this for all V vertices, the total time spent exploring edges becomes O(V * V) or O(V^2).
    • Therefore, the total time complexity for DFS using an adjacency matrix is O(V^2). This can be less efficient than the adjacency list approach, especially for sparse graphs where E is much smaller than V^2.

Note

Because O(V + E) is generally faster than O(V^2) (especially when graphs aren’t densely connected), adjacency lists are the preferred way to represent graphs for DFS implementations.

Space Complexity of DFS

Space complexity tells us how the memory usage of an algorithm grows with the input size. For DFS, we need memory for a few things:

  1. Storing the Graph: This depends on the representation.

    • Adjacency List: Requires O(V + E) space.
    • Adjacency Matrix: Requires O(V^2) space.
    • (Note: This storage cost is often considered part of the input size and sometimes excluded from the auxiliary space complexity analysis, which focuses on the extra space used by the algorithm itself.)

  2. Tracking Visited Nodes: We need a way to remember which nodes we’ve already visited to avoid processing them again and getting stuck in infinite loops (in graphs with cycles). This typically uses an array or hash set, requiring O(V) space.

  3. The Recursion Stack (or Explicit Stack):

    • The standard DFS algorithm is often implemented recursively. Each recursive call adds a frame to the system’s call stack. In the worst-case scenario (e.g., a graph that is just a long path), the recursion depth can go up to V. This means the space used by the call stack is O(V).
    • If you implement DFS iteratively using your own stack data structure, this stack will also store vertices, and in the worst case, it might hold up to O(V) vertices.

Considering the space needed for the visited set and the recursion/explicit stack, the auxiliary space complexity (extra space beyond the input graph storage) of DFS is O(V).

Factors Influencing Complexity

  • Graph Representation: As seen above, using an adjacency list (O(V + E) time) is typically more efficient time-wise for DFS than an adjacency matrix (O(V^2) time), especially for sparse graphs where E is much smaller than V^2.
  • Graph Structure: For dense graphs (where E is close to V^2), the O(E) part dominates O(V+E), making it closer to O(V^2), similar to the matrix approach. For sparse graphs (where E is closer to V), the complexity is closer to O(V).
  • Connectedness: If the graph is disconnected, DFS needs to be started from a node in each connected component to visit all vertices. However, the overall O(V + E) complexity still holds because each vertex and edge is processed at most a constant number of times across all DFS runs.

Conclusion

In summary, the time complexity of DFS is O(V + E) when using an adjacency list and O(V^2) when using an adjacency matrix. The space complexity is O(V), primarily due to the call stack and the visited set. Being mindful of these complexities enables you to make informed decisions when applying DFS to solve graph-related problems.

What’s Next?

Explore more about Depth First Search and related concepts: