# Understanding depth-limited BFS time complexity

I'm trying to implement graph power calculation using BFS. According to Wikipedia, BFS with depth limit k will suffice (I'm using adjacency list representation, my graphs are sparse, so adjacency matrix power is not optimal).

Complexity of BFS is O(V+E), running it for every vertex is trivially O(V*(V+E)). I also have depth limit k here and Wikipedia claims (in the page linked above) that running BFS with this constraint for every vertex will be O(V*E). Why is that? In the worst case when every vertex is in the "range" of k from every other vertex I'll have to search the entire graph V times, after all.

There are two cases.

First. $$V-1 \leq E$$. Then $$O(V \cdot (V + E))$$ and $$O(V \cdot E)$$ are equivalent.

Second. $$E < V-1$$. Then graph is disconnected and the biggest component has size at most $$E + 1$$. The whole algorithm will consist of $$V$$ BFS runs each on the component which has at most $$E + 1$$ vertices and at most $$E$$ edges. So each BFS run will take $$O(E)$$ time and the whole algorithm - $$O(VE)$$.

Note: this reasoning does not depend on $$k$$.

• Simple and elegant, thank you. Commented Apr 19, 2020 at 20:59
• I like this but don't understand how you got to the intermediate claim of $O(E^2)$ -- after bounding the size of each component, doesn't $O(VE)$ follow directly from the fact that we perform $V$ BFS operations, each on a (sub)graph of size at most $E+1$ vertices and $E-2$ edges? The $O(E^2)$ claim seems to imply that arbitrarily many isolated vertices can be processed/ignored in constant time. Commented Apr 20, 2020 at 17:35
• @j_random_hacker Thank you, fixed it. Obviously, there can't be $O(E^2)$ because for graph consisting of only isolated vertices it will imply $O(1)$ algorithm. Commented Apr 20, 2020 at 18:30
• Thanks, +1. Must try to remember this component size upper bound for the sparse case, feels like it could be useful. Commented Apr 20, 2020 at 19:34