Course contentsShow
← Computer Science
Lesson 727 of 2,87217. Graph Traversal AlgorithmsFree lesson

Time and Space Complexity

Analyze O(V+E) runtime and O(V) space for topological sorting algorithms.

Time and Space Complexity of Topological Sorting

You'll learn: Why topological sorting runs in O(V+E) time and uses O(V) space—understanding the efficiency of both Kahn's and DFS-based approaches.


Why O(V+E) Time?

Both major topological sorting algorithms—Kahn's algorithm and DFS-based sorting—visit every vertex and every edge exactly once.

  • Vertices (V): Each vertex is processed once—either enqueued and dequeued (Kahn's) or visited during traversal (DFS).
  • Edges (E): Each edge is examined exactly once to check adjacency or reduce in-degrees.

Think of it like inspecting a course prerequisite map: you look at each course once and check each prerequisite arrow once. No course or arrow is revisited.

Kahn's Algorithm Breakdown

  • Initialize in-degrees: O(E) — scan all edges
  • Process vertices with zero in-degree: O(V)
  • Reduce in-degrees for neighbors: O(E) total across all iterations
  • Total: O(V + E)

DFS-Based Algorithm Breakdown

  • Visit each vertex once: O(V)
  • Explore each edge once: O(E)
  • Push to result stack during backtracking: O(V)
  • Total: O(V + E)

Why O(V) Space?

Space complexity comes from auxiliary data structures:

  • Queue/Stack: Stores vertices temporarily — at most V vertices
  • In-degree array or visited flags: One entry per vertex — O(V)
  • Result list: Stores the sorted order — exactly V vertices
  • Call stack (DFS): Depth at most V in worst case

The graph itself (adjacency list or matrix) is input, not counted separately in auxiliary space analysis.


Key Takeaway:
Topological sorting algorithms run in O(V+E) time because they visit every vertex and edge exactly once, and use O(V) auxiliary space for tracking vertex states and results.