Breadth-First Complexity

Question

Closed this issue 9 years ago · 2 comments

Why does Breadth-First runs give O(n^2) complexity?

Answer 1 · 2016-02-04T13:58:57.000Z

Still remains that, with p = 1 (strongly connected graph), we should get O(n^2).

Answer 2 · 2016-02-04T14:14:50.000Z

With p = 1 it gets a strange behavior, I suspect that you should pass 1.0.
With p = 0.9: https://plot.ly/~affo/22/bf-p-09-quadratic/