2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Can you give the reference to the analysis ? $\endgroup$ – w00d Mar 1 '15 at 19:59
  • $\begingroup$ Here it is: en.wikipedia.org/wiki/Kosaraju%27s_algorithm#Complexity $\endgroup$ – nightmarish Mar 1 '15 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 '15 at 0:07
1
$\begingroup$

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$.

$\endgroup$
  • $\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$ – nightmarish Mar 1 '15 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$ – Yuval Filmus Mar 1 '15 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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