CODEWITHSUNDEEP
algorithmbig-odijkstra
Nikola
Nikola

Reputation: 2132

Why is the number of edges ignored in the big-O notation

I am having a hard time understanding Dijkstra's big O notation exactly. I have a question regarding Dijkstra with an unsorted array.

As from Wikipedia:

The simplest implementation of the Dijkstra's algorithm stores vertices of set Q in an ordinary linked list or array, and extract minimum from Q is simply a linear search through all vertices in Q. In this case, the running time is O(|E| + |V|^2) = O(|V|^2).

I have myself implemented the algorithm in my application, I know how it works. I do not understand why O(|E| + |V|^2) = O(|V|^2) or why the number of edges |E| is ignored?

Considering as pseudo code my Dijkstra looks something like:

for all vertices, current u
     for each neighbor v of u:
          .. do stuff
end for

This is how I explain to myself the O(|V|^2), but I do not understand how do they get the |E| and then remove it?

Upvotes: 1

Views: 888

Answers (2)

Gene
Gene

Reputation: 46960

When we say some characteristic (time, space, etc.) of an algorithm (let's call this characteristic T(N)) is "O(f(N))" for some function f, we are saying this:

For all values of N larger than some minimum, (we don't care what that minimum is, just that it exists), we can be sure T(N) < k(f(N)) for some positive constant k.

Well it turns out that any function f(N) with a squared term grows so fast that it eventually becomes larger (i.e. we can always find a minimum N where for all larger values f is larger) than any function with only linear terms, no matter what constants might magnify those linear terms.

This means that the number of edges in a graph - which can number up to (|V|^2+|V|)/2 (note the squared term) grows so much faster than the number of edges that - for purposes of big-O - it can be ignored.

For intuition, a graph with 1000 vertices can have about half a million edges. So the number of vertices is only 0.2% the number of edges. The bigger the graph, the more stark this disparity.

Upvotes: 2

Karoly Horvath
Karoly Horvath

Reputation: 96258

You can safely assume that |E| < |V|^2, so you can remove the slowly growing parts which are dominated (standard oh notation stuff...).

Explanation:

If you had edges between every vertices, that would be still only E = V*(V-1)/2 edges.

Upvotes: 2

Related Questions