Kosaraju's algorithm's time complexity

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

• using an adjacency list representation gives a time complexity of $\Theta(V+E)$.

• 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?

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

StackExchange Computer Science Q#39955, answer score: 2