Time complexity for both Kosaraju and Tarjan is . Kosaraju: First DFS takes to visit all nodes and edges. Building the transpose graph takes . Second DFS on the transpose graph takes . Total: .
Tarjan: One DFS pass with extra bookkeeping for , , and stack operations. Each node and edge is visited once. Total: . Building the condensation graph: to iterate over all edges.
Space complexity is for the data structures used.