# Why is the complexity of BFS O(V+E) instead of O(V*E)?

CLRS pseudocode:

begin
for each vertex u in G.V - {s}, do
u.color := white
u.d := infinity
u.p := NIL
done
s.color := green
s.d := 0
s.p := NIL
Q := NULL
insert s into Q
while Q is not null, do
u = delete from Q
for each v in adjacent to u, do
if v.color = white
v.color := green
v.d := u.d + 1
v.p := u
insert v into Q
end if
done
u.color = dark_green
done
end
`

In the clrs it says that the insertion and deletion operations with the queue require an O (1) time, so the total time of operations with the queue is O (V). (V because each vertex is visited at least once). instead the time to inspect the adjacency list of each node is O (E). Then we have another O (V) for initialization. So the total time is O (V + E) which in the worst case becomes O (V ^ 2), this depends on whether the graph is dense or not.

Now my question is: Since we have two cycles nested the complexity shouldn't be O (V * E), I can't understand why a sum operation is performed instead of multiplying.

• Imaging node $i$ has out-degree $d_i$ (the number of neighbors). Now you'll agree that since every node is visited only once we have for both loops combined: $\sum_{i=1}^{n} (1 + d_i)$ ($1$ is just the constant cost, $d_i$ the cost of the inner loop). So what does $\sum_{i = 1}^n d_i$ evaluate to? Oct 9, 2022 at 18:12
• di should evaluate all edges so it should cost O (E) with E varying between 1 and V ^ 2 depending on the density of the graph. (perhaps on the summation you should use V instead of n.) Oct 9, 2022 at 18:56

I will suppose here that the graph is undirected, but the same reasonning can be done with a digraph.

Using an implemention of a graph as an array of adjacency lists, the adjacency list of any vertex $$v$$ is its number of neighbors, $$\deg(v)$$.

The BFS inspects each adjacency list at most once during the graph traversal (and exactly once if the graph is connected). That means that the total complexity is: $$\mathcal{O}\left(\sum\limits_{v\in V}(\deg(v) + 1)\right)$$ Here, the $$+1$$ is necessary, as inspecting an adjacency list costs $$\mathcal{O}(1)$$ time, even if the list is empty. Now, a very useful formula for complexity on graphs is: $$\sum\limits_{v\in V}\deg(v) = 2|E|$$ It can be proven quite easily when noting that each edge increases the sum of degrees by two (one for each extremity).

Finaly, we conclude that the complexity is: $$\mathcal{O}\left(\sum\limits_{v\in V}(\deg(v) + 1)\right) = \mathcal{O}(2|E| + |V|) = \mathcal{O}(|E| + |V|)$$

• all very clear thanks for the explanation Oct 9, 2022 at 19:41
• @mimmolg99 If you want to be more precise, the complexity is $\mathcal{O}(|E_C| + |V|)$, where $E_C$ is the set of edges of the connected component $C$ of the vertex $s$. Oct 9, 2022 at 19:46
• it is correct to say that in the best case then the complexity will be O (V) in the worst case it will be O (V ^ 2) and in the average case O (E + V). In the best case I think it is O (V) because E should be 1 while in the worst case it should be V ^ 2. what do you think? Oct 9, 2022 at 19:52
• While it is true that the best case is $\mathcal{O}(|V|)$ and the worst case is $\Theta(|V|^2)$, you can't really say that the average case is $\mathcal{O}(|E| + |V|)$ because 1) it is always $\mathcal{O}(|E| + |V|)$. 2) average complexity implies that you consider a certain random distribution of graphs (and with the uniform distribution over all graphs with $|V|$ vertices, the average number of edges is $\Theta(|V|^2)$). Oct 9, 2022 at 20:01
• I understand.. thanks 🙏 Oct 9, 2022 at 20:21