Running time of Breath-First-Search — Proof

Running time of Breath-First-Search is (V+E), where V — number of vertexes and E — number of edges.

Pseudocode for BFS.

Image for post
Image for post

· Enqueue and dequeue operations take O(1) time, so the total time for queuing is O(V).

· Since each adjacency list is explored at most once the sum of all the adjacency list is O(E). So the total time for exploring adjacency lists is O(E).

Therefore the total running time of BFS is O(V+E).

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store