Search code examples
graphtime-complexityspace-complexity

graph time and space complexity representations


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?


Solution

  • 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.