BFS is slower than DFS. DFS is faster than BFS. 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.
Complexity Of Depth-First Search Algorithm If the entire graph is traversed, the temporal complexity of DFS is O(V), where V is the number of vertices.
In this notation, the E is the total number of edges in the graph. if the graph is represented in adjacency matrix then time complexity would be O(V*V) right? Because each time we pop the vertex from the q, we have to traverse all the vertex to find the adjacency vertex.
The space complexity for BFS is O(w) where w is the maximum width of the tree. For DFS, which goes along a single 'branch' all the way down and uses a stack implementation, the height of the tree matters. The space complexity for DFS is O(h) where h is the maximum height of the tree.
Your sum
v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)
can be rewritten as
(v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]
and the first group is O(N)
while the other is O(E)
.
DFS(analysis):
O(1)
timeO(n + m)
time provided the graph is represented by the adjacency list structureΣv deg(v) = 2m
BFS(analysis):
Li
O(n + m)
time provided the graph is represented by the adjacency list structureΣv deg(v) = 2m
Very simplified without much formality: every edge is considered exactly twice, and every node is processed exactly once, so the complexity has to be a constant multiple of the number of edges as well as the number of vertices.
An intuitive explanation to this is by simply analysing a single loop:
So the total time for a single loop is O(1)+O(e). Now sum it for each vertex as each vertex is visited once. This gives
For every V
=>
O(1)
+
O(e)
=> O(V) + O(E)
Time complexity is O(E+V)
instead of O(2E+V)
because if the time complexity is n^2+2n+7 then it is written as O(n^2).
Hence, O(2E+V) is written as O(E+V)
because difference between n^2 and n matters but not between n and 2n.
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