Menu
I was wondering what is the time complexity of BFS, if I use:
Is it same as their space complexity?
274
The Time complexity of BFS is O(V + E) when Adjacency List is used and O(V^2) when Adjacency Matrix is used, where V stands for vertices and E stands for edges.
Time Complexity of BFS = O(V+E) where V is vertices and E is edges. Time Complexity of DFS is also O(V+E) where V is vertices and E is edges.
Time complexity to go over each adjacent edges of a vertex is say O(N) , where N is number of adjacent edges. So for V number of vertices time complexity becomes O(V*N) = O(E) , where E is the total number of edges in the graph.
BFS: Time complexity is O(|V|) , where |V| is the number of nodes. You need to traverse all nodes. Space complexity is O(|V|) as well - since at worst case you need to hold all vertices in the queue.
The complexity of BFS implemented using an Adjacency Matrix will be O(|V|²). And that when implemented by an Adjacency List is O(|V| + |E|).
Why is it more in the case of Adjacency Matrix?
This is mainly because every time we want to find what are the edges adjacent to a given vertex 'U', we would have to traverse the whole array AdjacencyMatrix[U], which is ofcourse of length |V|.
Imagine the BFS progressing as frontiers. You take a starting vertex S, which is at level 0. All the vertices adjacent to S will be at level 1. Then, we mark all the adjacent vertices of all vertices at level 1, which don't have a level, to level 2. So, every vertex will belong to only one frontier. Each of these frontiers correspond to different levels. And when an element is in a frontier, we check once for its adjacent vertices, which takes O(|V|) time. As, the frontier covers |V| elements over the course of the algorithm, the total time would become O(|V| * |V|) which is O(|V|²).
The complexity difference in BFS when implemented by Adjacency Lists and Matrix occurs due to the fact that in Adjacency Matrix, to determine which nodes are adjacent to a given vertex, we take O(|V|) time, irrespective of the number of edges. Whereas, in Adjacency List, the edges that are immediately available to us, thus it takes time proportional to the number of adjacent vertices, which on summation over all vertices |V| is |E|. So, BFS by Adjacency List gives O(|V| + |E|).
129
Time complexity necessarily depends on the representation.
As this link suggests, the time complexity with and adjacency list is O(V + E), and with an adjacency matrix is O(V2).
43
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
