I wonder why graph algorithms time and space complexities are mostly represented using |E| and |V| instead of V and E. Every other algorithm's time and space complexities are represented using normal alphabets like N or NlogN. Why the graph algorithms are represented in the mod(|E|) like way?
In graph algorithms, both E
and V
are sets, not numbers. E
is the set of edges and V
is the set of vertices.
The complexity function is of numerical values. There is no meaning in log(E)
or E^2
, unless you refer to the size of the set. This is exactly what the absolute value does for sets, |X|
means the size of the set X
. This means, |E|
and |V|
respectively are the number of edges and vertices in the graph.
When you usually see n
, it means the size of the input. In graphs, we split it to |V|
and |E|
.
A common notation for graphs is using |V|=n
and |E|=m
, and then you use n,m
, like you are used to in other places.