The difference between dense graph and sparse one
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 &gt; 0$. You must analyze the performance of your algorithm under either type of family as inputs.

This definition is from Diestel's Graph Theory.