# Why do Tarjan's and Kosaraju's algorithms for finding strongly connected components have the same running-time complexity?

I followed an explanation of Kosaraju's and Tarjan's strongly-connected components algorithms, and they say that both have O(|V|+|E|) time complexity.

That didn't make sense to me since Kosaraju uses two DFS passes and computes the transposed graph, but Tarjan's use only one DFS.

• You seem to think that Landau notation is way more useful/informative than it really is. – Raphael Aug 23 '16 at 15:12

Both algorithms have running times in $\Theta(|V| + |E|)$; that does not preclude one of them being $2^{100}$ times faster than the other for all $n \leq 2^{100}$.