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

Bitartrate

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.

Ingurgitate

I dont think that this post properly answer the question. Similar answer with O(V^99) also properly upper-bound the alghoritm, but this is not what you actually want to know. – Paddock

Part of the challenge here is that the notation is overloaded. If you let O(V + E) denote the class of all functions bounded asymptotically by V + E, then O(V + E) != O(V^2) because there are functions in the class O(V^2) that aren’t in the class O(V + E). The answer I gave shows this by giving an explicit example of a runtime meeting these properties. However, it is true that any function that is O(V + E) is also O(V^2), and O(V^99), for that matter. After all, a function whose runtime is O(1) is also O(V + E), so the original bound of O(V + E) might not be tight. – Ingurgitate

I did not say your post is "wrong", there are only correct statements. But I (personally) think this answer can be misleading. A lot people can think "ok, I can just replace E with V^2" but they are not aware of losing big part of information. Also that it is not true for graphs with properties "average edges from node" and "maximum edges from nodes" set to constant. For example binary tree has maximum number of edges=3(two childs and parent), therefore E <= 3*V and O(V+E)=O(V+3*V)=O(4V)=O(V). This alghoritm will be linear for all binary trees, not V^2 – Paddock

I see what you’re saying. It seems like the concern here is how much we can assume about the background of people reading this answer. If you know that big-O represents an upper bound, then I think this answer would work well. If you’re not familiar with that idea, though, I agree that this could be confusing. – Ingurgitate

Answer 2

If you want to size it for any graph that can be completely randomized, then yes, you can count maximum edges based on number of nodes.

The reason why you will usually see counting E and V independently is the reality. And in reality complete graphs are not common. Well even in theory you can say that you have graph with N nodes and average edges from node is some constant number, i.e. 10.

For example if you want to find fastest path, you can implement Dijsktra for that. If you use real roads and you map the whole world, there will be a lot vertices and most of them will be limited to 4 edges (each vertex is crossroad, usually you have 4 options there), there will be few with more of them, but not much and even those are limited (you can have only finite number of roads from one crossroad).

So if the increasing the size (vertices) of graph does not increase average number of edges from nodes, you want information that counts E and V independently.

For example that Dijkstra in real world has linear complexity. But using Dijsktra for any graph can have up to V^2 complexity. But if you make program that is finding something in real life, you need to know that the complexity will be linear.

Paddock

Answer 3

No, O (|V| + |E|) is not equivalent to O (|V|^2). Here's why.

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

Perhaps this assumes that the graph is somehow given explicitly, we have to receive it as input in order to be able to work with it, and the total input size of edges is O (|V| + |E|) = n.

But we don't always have to receive the input once, then run an algorithm once. In some cases, we receive the input graph and then run the algorithm many times, so we are interested in its complexity regardless of the input size. In some other cases, the graph is given implicitly, so the input does not take much time.

Example: consider the knight's graph on a k * k chessboard: the graph where vertices are chessboard squares and edges are knight's moves. An example problem to solve is this: given two squares, find the knight's path between them which is shortest in the number of moves. An obvious algorithm to solve the problem is breadth-first search which takes O (|V| + |E|) time (we can do better but that's beside the point.)

Here, the input has size O (1): it's just the size of the board, k, and coordinates of two squares on it. We don't have to read or explicitly construct the graph at any time: it is given implicitly by the size k. In each vertex, we can enumerate all (up to 8) edges from this vertex in O (1). In terms of k, |V| = O (k), |E| <= 8 k so |E| = O (k), so we also have O (|V| + |E|) = O (k). On the other side, O (|V|^2) = O (k^2) which is a looser bound than O (k).

Consequently, in this example, O (|V| + |E|) is different from O (|V|^2), so they are generally not equivalent.

Sweepstakes

Answer 4

No

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.

Unless your input is specifically restricted to a simple graph then any non-simple graph can have multiple edges connecting pairs of vertices and looping edges connecting to a single vertex.

Imagine a very simple road system of connecting roundabouts around a town:

• Roundabouts are connected (i.e. a pair of adjacent vertices) by multiple edges which could be:
  • Directed edges (i.e. roads which may or may not come as matched pairs with opposing directions of travel); and
  • Undirected edges (i.e. footpaths and/or cycle paths on either side of the road)
• Each roundabout (vertex) can also have its own associated looping edges:
  • Directed edges (the road orbiting the roundabout);
  • Undirected edges (footpaths and/or cycle paths going under subways/over bridges and crossing the roads radiating from the roundabout).

So, even for this simplified real-world example, the graph is not simple and there are multi-edges and looping edges and if O(|E|) = O(|V|³) then O(|V|+|E|) > O(|V|²).

Nonjoinder