I've reading up on Kosaraju's algorithm to compute the strongly connected components of a directed graph and I found that

  1. using an adjacency list representation gives a time complexity of $\Theta(V+E)$.
  2. using an adjacency matrix representation gives a time complexity of $O(V^{2})$.

Why $\Theta$ in the first case and $O$ in the second case?

  • 1
    $\begingroup$ Can you give the reference to the analysis ? $\endgroup$
    – w00d
    Mar 1, 2015 at 19:59
  • $\begingroup$ Here it is: en.wikipedia.org/wiki/Kosaraju%27s_algorithm#Complexity $\endgroup$ Mar 1, 2015 at 20:02
  • $\begingroup$ @failexam Please include that in the question. You may also want to check the references Wikipedia lists, or find the analyses on Google Scholar. $\endgroup$
    – Raphael
    Mar 2, 2015 at 0:07

1 Answer 1


Any algorithm for computing strongly connected components must examine at least $\binom{|V|}{2}$ entries in the worst case (proof below). In particular, since Kosaraju's algorithm is correct, its (worst-case) complexity is $\Omega(|V|^2)$, and so also $\Theta(|V|^2)$. There is no particular reason why Wikipedia used big O for one and bit $\Theta$ for the reader – probably a different author.

Edit: One possible reason for using big O rather than big $\Theta$ is that sometimes the algorithm is lucky and runs faster. Whether this happens or not could depend on the particular implementation of DFS.

Suppose $A$ is an algorithm examining less than $\binom{|V|}{2}$ entries. We will show that the algorithm cannot always know what the strongly connected components are. Run the algorithm, and for each entry of the adjacency matrix queried by the algorithm, return $0$. When the argument terminates, there are more than $\binom{|V|}{2}$ off-diagonal entries not queried, and in particular there exist vertices $i \neq j$ so that neither the $(i,j)$ nor the $(j,i)$ entry are queried. We could complete the adjacency matrix in two different ways: the all zeroes matrix, or the one in which both these entires are $1$. In the former case, there are $n$ connected components, in the latter, only $n-1$.

  • $\begingroup$ So, you mean that, for this particular case, big omega and big oh are the same, so they give the same big theta? $\endgroup$ Mar 1, 2015 at 22:52
  • $\begingroup$ They are definitely the same in the worst-case. Perhaps on some graphs the algorithm runs faster, depending on the implementation of DFS, though for most implementations that probably doesn't happen. $\endgroup$ Mar 1, 2015 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.