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.