Is O(V+E) equivalent to O(V^2)?

Question

My question is about whether O(V+E) = O(V^2).

Basically, if O(V+E) is linear time such that V+E = n, wouldn't O(V^2) also be linear time?

I assume the worst-case/upper bound for O(V+E) is an edge between each vertex, which would result in (V-1)^2 edges. I also assumed that that can be considered V^2, so I would think that that would be equivalent to O(V^2).

Answer 1

Any runtime that is O(V + E) is also O(V²) for the reason you articulated (E = O(V²)). That doesn’t mean that it’s a good idea to say that the runtime is O(V²), though, since that’s a less precise bound. In sparse graphs, O(V + E) is a much tighter bound than O(V²).

However, the converse isn't true. For example, consider this algorithm:

for each node v in V:
   for each node u in V:
       print (v, u)

This algorithm has a runtime of Θ(V²) and its runtime doesn't depend on the number of edges in the graph. Therefore, it would not be correct to say that the runtime is O(V + E), since in a graph with a low number of edges (say, a tree) the bound of O(V + E) would incorrectly predict that the runtime is linear in the number of nodes, whereas the runtime of O(V²) would correctly upper-bound the runtime at a quadratic.