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

Question

The basic algorithm for BFS:

set start vertex to visited

load it into queue

while queue not empty

   for each edge incident to vertex

        if its not visited

            load into queue

            mark vertex

So I would think the time complexity would be:

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges) 

where v is vertex 1 to n

Firstly, is what I've said correct? Secondly, how is this O(N + E), and intuition as to why would be really nice. Thanks

Engracia

I found this explanation very clear and understandable – Accessary

As Kaveh's link shows, the complexity has great relation with its used structure, O(V+E) when using the adjacency list. Since both DFS and BFS can use this and they both maintain one visited structure to ensure the spanning tree with no circuits, they both have time complexity O(V+E). – Anchor

Answer 1

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

Divulge

But every vertex must be extracted from queue, and this is log(|Q|) What about this part? – Viosterol

log(|Q|) < log(N) < N hence you can safely ignore the term in the asymptotic – Divulge

If in an adjacency list, each vertex is connected to all other vertices the would the complexity be equivalent to O(V+E)=O(V+V^2)=O(V^2). E=V^2 because the most number of edges = V^2. – Cavour

According to your answer, won't the complexity become O(V+2E)? Since every edge might have a common edge with another edge? – Babble

The constant terms can be dropped. – Divulge

"But every vertex must be extracted from queue, and this is log(|Q|)" Absolutely not! It's a linked list not a heap queue. – Cist

Answer 2

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

Eudo

tnx for the edit i'm new here so i still try to manage with the edit screen :) – Eudo

thanks for being specific by mentioning that the graphs are to be represented by the adjacency list structure, it was bugging me why DFS is O(n+m), I would think it was O(n + 2m) because each edge is traversed twice by backtracking. – Ansela

Answer 3

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.

Pavonine

Much easier to understand than math notation without further explanation although that is what Google is for. – Conduce

why is every edge considered exactly twice? – Akron

Each vertex is visited at most one time, because only the first time that it is reached is its distance null , and so each vertex is enqueued at most one time. Since we examine the edges incident on a vertex only when we visit from it, each edge is examined at most twice, once for each of the vertices it's incident on. See Source – Pavonine

Answer 4

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)

as we are visiting each node only once.

Benedictbenedicta

Answer 5

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.

Psychosis

@Am_I_Helpful somebody is asking above for 2E in big-oh notation....that why 2 is not considered in time complexity. – Psychosis

@Am_I_Helpful just see the post above my answer....there the user named Kehe CAI has written "I think every edge has been considered twice and every node has been visited once, so the total time complexity should be O(2E+V)." So i answered acordingly....Got it !!! – Psychosis

I removed my downvote only because you edited your answer, – Sidekick

Answer 6

I think every edge has been considered twice and every node has been visited once, so the total time complexity should be O(2E+V).

Paries

Even I feel the same. Can anyone give further explanation on this ? – Woodley

Big O analysis ignores the constant. O(2E+V) is O(E+V). – Highfalutin

Yes, in Big O analysis, it is common to drop the constant and non-dominant parts. – Mccann

Answer 7

Short but simple explanation:

I the worst case you would need to visit all the vertex and edge hence the time complexity in the worst case is O(V+E)

Advisable

Answer 8

In Bfs, each neighboring vertex is inserted once into a queue. This is done by looking at the edges of the vertex. Each visited vertex is marked so it cannot be visited again: each vertex is visited exactly once, and all edges of each vertex are checked. So the complexity of BFS is V+E. In DFS, each node maintains a list of all its adjacent edges, then, for each node, you need to discover all its neighbors by traversing its adjacency list just once in linear time. For a directed graph, the sum of the sizes of the adjacency lists of all the nodes is E(total number of edges). So, the complexity of DFS is O(V + E).

Belorussia

Answer 9

It's O(V+E) because each visit to v of V must visit each e of E where |e| <= V-1. Since there are V visits to v of V then that is O(V). Now you have to add V * |e| = E => O(E). So total time complexity is O(V + E).

Stowage