Why is the BigO of adjacency list for a graph is (V + E) and not (V^2)?

Question

Correct me if my thinking is wrong. I think that BigO(V + E) = BigO(V^2).

Below is my thinking:
Edges in a complete graph = n*(n-1)/2.

Switching from E and V to n because it is easier for me to think that way.

E = n*(n-1)/2
V = n

BigO(V + E) => BigO(n + n*(n-1)/2) => BigO(n^2)

Switching n back to V.

=> BigO(v^2)

am I missing something? Why use BigO(V + E)? Why not use BigO(V^2)?

Answer 1

The memory usage of an adjacency list is directly proportional to the sum of the number of nodes and the number of edges. This is because each node has an associated list of the edges leaving it, and each edge appears at most twice (once for each node it touches in an undirected graph, or once for a directed graph). This means that the space usage is Θ(V + E).

You gave two different asymptotic bounds on the memory usage, O(V + E) and O(V²). Both of these bounds are correct, but one is tighter than the other. The O(V + E) bound more precisely indicates that there are two semi-independent quantities that go into the space usage, the number of nodes and the number of edges, and is more precise. The O(V²) bound is less precise, but gives a worst-case bound on the total memory usage by considering the maximum possible value of E in terms of V. In other words, the O(V + E) bound is much more useful if you're trying to precisely pin down the memory usage, but the O(V²) bound is better if you're worried about the worst-case memory usage.

(A quick note: the statement "an adjacency list is O(V + E)" isn't a meaningful sentence. Since big-O quantifies growth rates of functions, it would be like saying "an adjacency list is 95,201" - it's meaningless because you're comparing an object with a number. However, you can say "the space usage of an adjacency list is O(V + E)" because the space usage of an adjacency list is an actual numeric quantity.)