Breadth First Search time complexity analysis

Question

The time complexity to go over each adjacent edge of a vertex is, say, O(N), where N is number of adjacent edges. So, for V numbers of vertices the time complexity becomes O(V*N) = O(E), where E is the total number of edges in the graph. Since removing and adding a vertex from/to a queue is O(1), why is it added to the overall time complexity of BFS as O(V+E)?

Coble

Answer 1

I hope this is helpful to anybody having trouble understanding computational time complexity for Breadth First Search a.k.a BFS.

Queue graphTraversal.add(firstVertex);

// This while loop will run V times, where V is total number of vertices in graph.
while(graphTraversal.isEmpty == false)

    currentVertex = graphTraversal.getVertex();

    // This while loop will run Eaj times, where Eaj is number of adjacent edges to current vertex.
    while(currentVertex.hasAdjacentVertices)
        graphTraversal.add(adjacentVertex);

    graphTraversal.remove(currentVertex);

Time complexity is as follows:

V * (O(1) + O(Eaj) + O(1))
V + V * Eaj + V
2V + E(total number of edges in graph)
V + E

I have tried to simplify the code and complexity computation but still if you have any questions let me know.

Coble

This was really helpful some 2 years later, thanks! Should the Eaj portion in the equation be wrapped as O(Eaj) though? – Collado

Yes @Collado – Johnny

One thing we can add that 'Eaj' max could be 'V-1' (total vertices in case of fully connected graph) and Min 0 (In case of disconnected graph), in that case equation: V * Eaj + 2V for max = 2V + V(V-1) = O(V^2) and for min O(V). – Dolores

O(1) + O(Eaj) + O(1) is not just O(Eaj)? – Chalcography

It should be noted that in order avoid cycles or visiting vertices multiple times, visited vertices should be marked – Notus

The answer is mostly correct, but your notation is not. Specifically the V * Eaj part. The calculation is a sum over all vertices, not a multiplication by V. Summing O(1) over V is O(V) (even that is not entirely correct - the "O(1)" must be uniformly bounded over all vertices, which is not obvious); but the sum of Eaj is E - and that is the correct computation - while if you were to sum V * Eaj you would get V * E. It's just bad notation though, not something incorrect in the thought process. – Pycnidium

The calculation of time complexity is not correct. The while loop will actually take O(E) time. According to Cormen's book, the initialisation of vertices takes O(V) time. That's why total complexity is O(V+E) – Kelleykelli

If anyone is still confused with the calculation. Check out: https://mcmap.net/q/195924/-why-is-the-complexity-of-bfs-o-v-e-instead-of-o-e-duplicate, this answer its much more simple and concise. – Cockleboat

Answer 2

Considering the following Graph we see how the time complexity is O(|V|+|E|) but not O(V*E).

Adjacency List

V     E
v0:{v1,v2} 
v1:{v3}
v2:{v3}
v3:{}

Operating How BFS Works Step by Step

Step1:

Adjacency lists:

V     E
v0: {v1,v2} mark, enqueue v0
v1: {v3}
v2: {v3}
v3: {}

Step2:

Adjacency lists:

V     E
v0: {v1,v2} dequeue v0;mark, enqueue v1,v2
v1: {v3}
v2: {v3}
v3: {}

Step3:

Adjacency lists:

V     E
v0: {v1,v2}
v1: {v3} dequeue v1; mark,enqueue v3
v2: {v3}
v3: {}

Step4:

Adjacency lists:

V     E
v0: {v1,v2}
v1: {v3}
v2: {v3} dequeue v2, check its adjacency list (v3 already marked)
v3: {}

Step5:

Adjacency lists:

V     E
v0: {v1,v2}
v1: {v3}
v2: {v3}
v3: {} dequeue v3; check its adjacency list

Step6:

Adjacency lists:

V     E
v0: {v1,v2} |E0|=2
v1: {v3}    |E1|=1
v2: {v3}    |E2|=1
v3: {}      |E3|=0

Total number of steps:

|V| + |E0| + |E1| + |E2| +|E3| == |V|+|E|
 4  +  2   +  1   +   1  + 0   ==  4 + 4
                           8   ==  8

Assume an adjacency list representation, V is the number of vertices, E the number of edges.

Each vertex is enqueued and dequeued at most once.

Scanning for all adjacent vertices takes O(|E|) time, since sum of lengths of adjacency lists is |E|.

Hence The Time Complexity of BFS Gives a O(|V|+|E|) time complexity.

Rollie

Thanks, Nice explanation. – Messiah

Answer 3

The other answers here do a great job showing how BFS runs and how to analyze it. I wanted to revisit your original mathematical analysis to show where, specifically, your reasoning gives you a lower estimate than the true value.

Your analysis goes like this:

• Let N be the average number of edges incident to each node (N = E / V).
• Each node, therefore, spends O(N) time doing operations on the queue.
• Since there are V nodes, the total runtime is the O(V) · O(N) = O(V) · O(E / V) = O(E).

You are very close to having the right estimate here. The question is where the missing V term comes from. The issue here is that, weirdly enough, you can't say that O(V) · O(E / V) = O(E).

You are totally correct that the average work per node is O(E / V). That means that the total work done asympotically is bounded from above by some multiple of E / V. If we think about what BFS is actually doing, the work done per node probably looks more like c₁ + c₂E / V, since there's some baseline amount of work done per node (setting up loops, checking basic conditions, etc.), which is what's accounted for by the c₁ term, plus some amount of work proportional to the number of edges visited (E / V, times the work done per edge). If we multiply this by V, we get that

V · (c₁ + c₂E / V)

= c₁V + c₂E

= Θ(V + E)

What's happening here is that those lovely lower-order terms that big-O so conveniently lets us ignore are actually important here, so we can't easily discard them. So that's mathematically at least what's going on.

What's actually happening here is that no matter how many edges there are in the graph, there's some baseline amount of work you have to do for each node independently of those edges. That's the setup to do things like run the core if statements, set up local variables, etc.

Duala

Answer 4

Performing an O(1) operation L times, results to O(L) complexity. Thus, removing and adding a vertex from/to the Queue is O(1), but when you do that for V vertices, you get O(V) complexity. Therefore, O(V) + O(E) = O(V+E)

Ambulance

Answer 5

One of the ways that I grasped the intuition of the time complexity O ( V + E) is that when we traverse the graph (let's take BFS pseudocode in Java):

for(v:V){ // segment 1
    if(!v.isVisited) {
        q = new Queue<>();
        q.add(v);
        v.isVisited = true
        while(!q.isEmpty) {
            curr  = q.poll()

            for(u: curr.adjacencyList ){ //Segment 2
                //do some processing
                u.isVisited = true
            }
        }
    }
}

As, we can see there are two important segments 1 and 2 which determines the time complexity.

Case 1: Consider a graph with only vertices and a few edges, sparsely connected graph (100 vertices and 2 edges). In that case, the segment 1 would dominate the course of traversal. Hence making, O(V) as the time complexity as segment 1 checks all vertices in graph space once.

Therefore, T.C. = O(V) (since E is negligible).

Case 2: Consider a graph with few vertices but a complete graph (6 vertices and 15 edges) (n C 2).

Here the segment 2 will dominate as the number of edges are more and the segment 2 gets evaluated 2|E| times for an undirected graph.

T.C. of first vertex processing would be, O(1) * O(2|E|) = O(E)

The rest of the vertex will not be evaluated for the segment 1 and would just add V-1 times of processing (since they are already visited in segment 2 which is O(V).

Thus, in this case its better to say T.C. = O(E) + O(V)

So, in the worst/best case of number of edges, we have

TC(taversing) O(E) + O(V) or

= O(E+V)

Leigh

Answer 6

I would just like to add to above answers that if we are using an adjacency matrix instead of a adjacency list, the time complexity will be O(V^2), as we will have to go through a complete row for each vertex to check which nodes are adjacent.

Drogue

Answer 7

You are saying that total complexity should be O(V*N)=O(E). Suppose there is no edge between any pair of vertices i.e. Adj[v] is empty for all vertex v. Will BFS take a constant time in this case? Answer is no. It will take O(V) time(more accurately θ(V)). Even if Adj[v] is empty, running the line where you check Adj[v] will itself take some constant time for each vertex. So running time of BFS is O(V+E) which means O(max(V,E)).

Joacimah

Answer 8

The answers I've seen here are correct, but there's a catch. Saying that BFS (or DFS) complexity is O(|V|+|E|) is only true if you need to traverse the whole graph, visiting each of its connectivity components. In this case, you can't take |V| out of the equation since you may need to start your BFS algorithms more than once if the graph is disconnected. Keeping in mind that when we compute complexity, we take into account all the atomic operations and treat them as O(1), your algorithm will have to start O(|V|) times.

However, if you only need to traverse one connectivity component, then the number of nodes in it is limited by |E| + 1, which gives us |V|=O(|E|), and the eventual complexity for this case is O(|E|).

It would be more proper to look at all the steps of the algorithm and count how many times it performs the atomic operations to get the O(|E|) result for the single connectivity component case, but the explanation above gives the general idea of why it's true.

Subduct