Compare Complexity of Graph Algorithm

Question

Assume I know that there is an algorithm of complexity
$ \mathcal{O}( log ( \vert V \vert^2 \vert E \vert ) ) $ for a Graph $G(E,V)$.

How do I compare this for example to the complexity of
$ \mathcal{O}( \vert V \vert^2 + \vert E \vert ) $ or other complexity algorithms on $G$.

There has to be a connection between $\vert E \vert$ and $\vert V \vert $ if I am right which is needed to solve this. But the only thing I found is $max .\vert E \vert = \frac{\vert V \vert }{2}(\vert V \vert -1)$, what does not help here and in many other cases.

Or should I just assume $max .\vert E \vert = \frac{\vert V \vert }{2}(\vert V \vert -1)$ and $min.\vert E \vert = \vert V \vert -1$ ?
Btw. must a vertex be connected via an edge to the graph per definition?

Answer 1

In general all we can say is that $0 \le |E| \le |V|^2$. Thus, $|E| = O(|V|^2)$.

For connected graphs, $|V|-1 \le |E| \le |V|^2$. For many problems, we can show that only connected graphs are of interest (e.g., if the graph is disconnected, we can decompose it into connected components and then solve the problem separately on each connected component). For these problems, $|E| = O(|V|^2)$ and $|E| = \Omega(|V|)$ (i.e., $|V| = O(|E|)$).

Answer 2

First of all $\min (|E|) = 0$ since the graph can be disconnected. $\min(|E|) = |V| - 1$, is true only for connected graphs. Whether a vertex is needed to be connected to the graph depends on the problem being considered. In general, a vertex can be isolated. So, in general, $0 \leq |E| \leq {{|V|}\choose{2}}$, if the graph is not a multi-graph. If the graph is a multi-graph then there is no upper limit to $|E|$.

Secondly if we are comparing $O((\log|V|^2||E|))$ against something like $O(|V|^2+|E|)$, former will be always better than the latter , since $O(\log(|V|^2)|E|) = O(\log|E|+2\log|V|)$.

So the question is, whether to analyze algorithms in terms of $|E|$ (i.e $|E|$ and $|V|$) or only in terms of $|V|$.

Of course what you say about needing to relate $|V|$ and $|E|$ is correct. However, whenever a complexity is stated in terms of $|E|$, it is better than, say, substituting $|V|^2$ for $|E|$. Note that $|E|$ is always $O(|V|^2)$ even for the cases when it is smaller, for example, for trees. $O()$ is upper bound.

If the analysis of an algorithm is in terms of $|E|$ than we get the complexity bound for all the cases, whether the graph is dense or sparse. Thus $|E||V|$-time algorithm is considered better than a $|V|^3$-time algorithm.

In the cases, if the graph is a tree, or a graph with a max degree $d=O(1)$, then $|E|$ is only $O(|V|)$. So, as an example, an $O(|E||V|)$ algorithm will be considered better than $O(|V|^3)$ algorithm. Thus, if we are able to do a tighter analysis, we are sure that the algorithm will fare better in case of non-worst case input.

As pointed by Raphael, $\Theta(|E|)$ is not same as $O(|V|^2)$. $\Theta$ analysis is better wherever applicable. But usually we don't give $\Theta$ analysis, because if we say some algorithm is $\Theta(f(n))$, and for some easy input the algorithm runs in $o(f(n))$ time, our statement will be wrong.