CODEWITHSUNDEEP
algorithmgraphbig-obreadth-first-search
levio_sa
levio_sa

Reputation: 145

Breadth First Search Time Complexity

I want to ask, why is the time complexity of BFS not O(V) instead of O(E+V)?

Reason being the queue storing elements to be checked is enqueued at most V times. So we have at most V entries in the queue. So enqueue occurs at most V times and enqueue is the most frequent operation occuring in bfs. So order should be O(V)

Upvotes: 1

Views: 103

Answers (1)

templatetypedef
templatetypedef

Reputation: 372664

Expanding on @beaker's comment:

You are completely correct that there are only O(|V|) total nodes enqueued during a full run of breadth-first search, for exactly the reason that you've mentioned. However, it's not the case that the enqueues are the most frequent operation performed during the BFS, so you can't go from this to claiming that the runtime is O(|V|).

In a BFS, whenever a node is dequeued from the queue, each of its neighbors is scanned to see whether it should also be added to the queue. This means that, across the full run of BFS, each edge is scanned at most once (if the graph is directed) or at most twice (if it's undirected, once when each endpoint is dequeued). Overall, that adds in O(|E|) additional work that must be done, which both explains where that other term comes from and shows why the dominant work isn't purely in enqueues and dequeues.

Hope this helps!

Upvotes: 2

Related Questions