Time Complexity Summary

Time complexity for both Kosaraju and Tarjan is $O(V + E)$. Kosaraju: First DFS takes $O(V + E)$ to visit all nodes and edges. Building the transpose graph takes $O(E)$. Second DFS on the transpose graph takes $O(V + E)$. Total: $O(V + E)$.

Tarjan: One DFS pass with extra bookkeeping for $disc$, $low$, and stack operations. Each node and edge is visited once. Total: $O(V + E)$. Building the condensation graph: $O(V + E)$ to iterate over all edges.

Space complexity is $O(V)$ for the data structures used.