3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The key is to investigate how |V| and |E| relate. Note that it is not per se clear how Landau notation works with multiple variables; see also here and here. $\endgroup$ – Raphael Feb 7 '16 at 18:07
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ sorry, I hat to edit the question. But thanks for the reply! $\endgroup$ – N8_Coder Feb 7 '16 at 11:54
  • 1
    $\begingroup$ But why should $ \vert E \vert \vert V \vert $ be better thant $\vert V \vert ^3$ ? That does not make sense in my eyes, because $E \in O( \vert V \vert ^2 ) $ as you said... $\endgroup$ – N8_Coder Feb 7 '16 at 13:57
  • $\begingroup$ @CompScif $O$ is only an upper bound. This discussion does not make any sense unless you talk $\Theta$. $\endgroup$ – Raphael Feb 8 '16 at 7:18
  • $\begingroup$ Right, CompSci is confused why $\Theta(E)$ is better than $O(|V|^2)$. I tried to explain in words rather than bringing another symbol. $\endgroup$ – Shreesh Feb 8 '16 at 7:23

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.