0
$\begingroup$

How to decide whether the following statement is correct?

O(E log E) and O(E log V) are equivalent regardless whether graph is dense or sparse

$\endgroup$

closed as unclear what you're asking by David Richerby, Evil, Rick Decker, Juho, Raphael Oct 26 '16 at 11:18

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Sep 27 '16 at 8:54
  • $\begingroup$ Which definition of "sparse" are you using? $\endgroup$ – Raphael Sep 27 '16 at 8:55
  • $\begingroup$ @Raphael The question may not be ideal, but I am surprised that you consider the word "sparse" to be unclear in this context. The word "sparse" is widely used in mathematics, and it is normally not considered a problem that it can mean slightly different things in different contexts. For example, a Toeplitz matrix is sparse, even so its corresponding (bipartite) graph is dense. But I don't see how any confusion could arise in the context of this question. $\endgroup$ – Thomas Klimpel Oct 26 '16 at 8:42
  • $\begingroup$ @ThomasKlimpel I'm not a big fan of promoting imprecision just because it "usually doesn't matter". For graphs in particular different notions of "sparse" exist and may cause different answers here, unless we discuss only connected graphs. $\endgroup$ – Raphael Oct 26 '16 at 11:16
1
$\begingroup$

You have to be careful with your definitions. For any graph, the number of nodes and the number of edges is a constant, so $O(V) = O(E) = (1)$. This is clearly not helpful.

Sparse and dense only make sense for a family of graphs $\{G_n\}_{n=1}^\infty$.

The edge density of a graph $G$ is the proportion of possible edges that a graph actually has:

$$ D = \frac{|E(G)|}{{|V(G)|}\choose{2}}. $$

The edge density of a family of graphs is

$$ D = \lim_{n \to \infty} \frac{|E(G_n)|}{{|V(G_n)|}\choose{2}}. $$

The family is sparse if $D = 0$ and dense if $D > 0$. You must analyze the performance of your algorithm under either type of family as inputs.

This definition is from Diestel's Graph Theory.

$\endgroup$
-1
$\begingroup$

In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph.

A sparse graph is a graph $G=(V,E)$ in which $|E|=O(|V|)$.

For example, consider a graph $G=(V,E)$ with n nodes. Suppose that the out-degree of each vertex in $G$ is some fixed constant k. Graph $G$ is a sparse graph because $|E|=k|V|=O(|V|)$.

[UPDATE] If $N$ and $E$ are the number of nodes and edges in a network respectively. $N^2$ possible edges in a fully connected network.

Sparseness $P = \frac{E} {N^2} $

If $P << 1$, then the network is sparse.

Source: MIT OpenCourseWare

A dense graph is a graph $G=(V,E)$ in which $|E|=O(|V|^2)$.

For example, consider a graph $G=(V,E)$ with n nodes. $|E|=f|V|^2=O(|V|^2)$.

How to decide whether the following statement is correct?

O(E log E) and O(E log V) are equivalent regardless whether graph is dense or sparse

In the case of $O(E log E)$ and $O(E log V)$,

asymptotically $log E \approx log V$ and only $E$ contributes to the result regardless the graph is dense or sparse.

Thus, $O(E log E) \approx O(E log V)$ for any dense or sparse graph.

$\endgroup$
  • $\begingroup$ You want to use some $\Omega$s there. $\endgroup$ – Raphael Sep 27 '16 at 12:16
  • $\begingroup$ "asymptotically log E ≈ log V" -- not always; consider $E \in O(\log V)$. "only E contributes" -- so you propose we always ignore logarithmic factors? $\endgroup$ – Raphael Sep 27 '16 at 12:18
  • $\begingroup$ Raphael has a point; you need lower bounds to make these definitions meaningful. If we have a family of graphs where $|E|=O(|V|)$ then it will also be the case that $|E|=O(|V|^2)$, so by your definitions, every graph would be dense. $\endgroup$ – Rick Decker Sep 27 '16 at 12:49
  • $\begingroup$ @Raphael thanks for the insight. Yes, when $E \epsilon O(logV)$, the graph is mostly disconnect and this solution wont work. Feel free to edit my solution. $\endgroup$ – Alwyn Mathew Sep 27 '16 at 12:51
  • 1
    $\begingroup$ "A sparse graph is a graph $G=(V,E)$ in which $|E|=O(|V|)$." It doesn't make sense to write that about a single graph: there is no such thing as "for all large enough $|V|$" when you're talking about a single graph. Density and sparsity are properties of families of graphs, not single graphs. $\endgroup$ – David Richerby Sep 27 '16 at 13:05

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