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

Question

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

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

I assume that the worst / upper bound for O(V+E) is the edges between each vertex, which will result in edges (V-1)^2 . I also suggested that this could be considered V^2 , so I would have thought that it would be equivalent to O(V^2) .

Answer 1

Any runtime that is O (V + E) is also O (V ² ) for the reason you formulated (E = O (V ² )). This does not mean that it is a good idea to say that the runtime is O (V ² ), although this is a less accurate estimate. In sparse graphs, O (V + E) is a much tougher boundary than O (V ² ).

However, the converse is not true. For example, consider this algorithm:

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

This algorithm has runtime & Theta; (V ² ), and its execution time does not depend on the number of edges in the graph. Therefore, it would be wrong to say that the runtime is O (V + E), since in a graph with a small number of edges (for example, in a tree) the estimate O (V + E) incorrectly predicts that runtime is linear in the number of nodes, whereas Runtime O (V ² ) correctly limits the runtime in quadratic mode.

Answer 2

If you want its size for any graph that can be completely randomized, then yes, you can calculate the maximum edges based on the number of nodes.

The reason you usually see that counting E and V independently is reality. And in fact, full graphs are not shared. Even in theory, you can say that you have a graph with N nodes, and the middle edges from node are some constant number, i.e. ten.

For example, if you want to find the fastest way, you can implement Dijsktra for this. If you use real roads, and you will display the whole world, there will be many peaks, and most of them will be limited to 4 edges (each peak is a crossroads, usually you have 4 options), there will be a little more, but not so many, and even those are limited (you can only have a finite number of roads from one intersection).

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

For example, Dijkstra in the real world has linear complexity. But using Dijsktra for any graph can have a complexity of V ^ 2. But if you are creating a program that finds something in real life, you need to know that the complexity will be linear.

Answer 3

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

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

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

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

Example : consider a knight’s graph on the chessboard k * k : a graph where the vertices are the squares of the chessboard and the edges are knightly movements. An example is the following task: given two squares, find the path of the knights between them, which is the shortest number of moves. The obvious algorithm for solving the problem is a breadth-first search , which takes O (|V| + |E|) time (we can do better, but this is not relevant.)

Here, the input has size O (1) : this is only the size of the board, k and the coordinates of two squares on it. We do not need to read or explicitly plot the chart at any time: it is specified implicitly by size k . At each vertex, we can list all (up to 8) edges from this vertex to O (1) . In terms of k , |V| = O (k) |V| = O (k) , |E| <= 8 k |E| <= 8 k so |E| = O (k) |E| = O (k) , so we also have O (|V| + |E|) = O (k) . On the other hand, O (|V|^2) = O (k^2) , which is a looser estimate than O (k) .

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

Answer 4

No

I assume that the worst / upper bound for O (V + E) is an edge between each vertex, which will result in (V-1) ^ 2 edges.

If your input is not specifically limited to a simple graph , then any complicated graph can have several edges connecting pairs of vertices and cycles connecting to one vertex.

Imagine a very simple road system for connecting roundabouts around a city:

• Carousels are connected (i.e. a pair of adjacent vertices) by several edges, which can be:
  • Directional ribs (i.e. roads that may or may not coincide with pairs with opposite directions of movement); and
  • Non-overlapping ribs (i.e. walking paths and / or bicycle paths on either side of the road)
• Each window (top) can also have its own connected loops:
  • Directional edges (road revolving around the roundabout);
  • Non-overlapping ribs (pedestrian paths and / or bicycle paths running under the metro / over bridges and crossing roads emanating from roundabouts).

Thus, even for this simplified example of the real world, the graph is not simple and has polyhedrons and edges of the cycle, and if O(|E|) = O(|V|³) then O(|V|+|E|) > O(|V|²) .