# 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.

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$$.
• 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
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 11, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}