Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why is the time complexity of both DFS and BFS O( V + E )

People also ask

Is time complexity of BFS and DFS same?

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.

What is the time complexity of a DFS?

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.

Why is time complexity of BFS O v E?

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.

What is the space complexity of BFS and DFS?

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):

  • Setting/getting a vertex/edge label takes O(1) time
  • Each vertex is labeled twice
    • once as UNEXPLORED
    • once as VISITED
  • Each edge is labeled twice
    • once as UNEXPLORED
    • once as DISCOVERY or BACK
  • Method incidentEdges is called once for each vertex
  • DFS runs in O(n + m) time provided the graph is represented by the adjacency list structure
  • Recall that Σv deg(v) = 2m

BFS(analysis):

  • Setting/getting a vertex/edge label takes O(1) time
  • Each vertex is labeled twice
    • once as UNEXPLORED
    • once as VISITED
  • Each edge is labeled twice
    • once as UNEXPLORED
    • once as DISCOVERY or CROSS
  • Each vertex is inserted once into a sequence Li
  • Method incidentEdges is called once for each vertex
  • BFS runs in O(n + m) time provided the graph is represented by the adjacency list structure
  • Recall that Σ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:

  1. visit a vertex -> O(1)
  2. a for loop on all the incident edges -> O(e) where e is a number of edges incident on a given vertex v.

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.