Removing non-constants in algorithm complexity
So basically I am implementing an algorithm for calculating the distances from one source node to any other node in a weighted plot, and if a node is in a negative loop, it detects and marks the node as such.
My question is about the total time complexity of my algorithm. Suppose that V
is the number of nodes and the E
number of edges.
The algorithm starts by asking E lines of input to indicate the edges of the graph and inserting it into the appropriate adjacency list. Such an operationO(E)
I apply the Bellman-Ford algorithm V-1
once to find out the distances, and then apply the algorithm V-1
again once to find the Nodes in a negative cycle. This is 2 * O(VE) = O(VE)
.
I am printing a vector of distances with a size V
to display distances and / or if the node is in a negative loop or not. O(V)
...
So, I guess my overall complexity will be O(VE + V + E)
. Now my question is, since VE is almost always greater than V + E (for large numbers it is always!), Can I reset V + E in difficulty and make it simple O(VE)
?
source to share
Yes, O(VE + V + E)
it simplifies to O(VE)
given that V and E represent the number of vertices and edges in the graph. For a highly connected schedule, E = O(V^2)
and so in this case VE + V + E = O(V^3) = O(VE)
. For a sparse plot E = O(V)
(note that this is not necessarily a tight upper bound), and therefore VE + V + E = O(V^2) = O(VE)
. In all cases O(VE)
, the corresponding upper bound for difficulty.
source to share
Yes, when you are dealing with asymptotic complexity, you always assume that V
and are E
very large (in theory, you study complex by calculating the limits as V
and E
approaching infinity). Pretty much the same thing, that you can write n^2 + n = O(n^2)
in your case VE + V + E
there O(VE)
.
Note that the worst-case Bellman-Ford difficulty is in fact O(VE)
, which confirms your reasoning.
source to share