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

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

The answer is


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


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.


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


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)

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)


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


Examples related to algorithm

How can I tell if an algorithm is efficient? Find the smallest positive integer that does not occur in a given sequence Efficiently getting all divisors of a given number Peak signal detection in realtime timeseries data What is the optimal algorithm for the game 2048? How can I sort a std::map first by value, then by key? Finding square root without using sqrt function? Fastest way to flatten / un-flatten nested JSON objects Mergesort with Python Find common substring between two strings

Examples related to time-complexity

Find common substring between two strings Why is the time complexity of both DFS and BFS O( V + E ) How to find time complexity of an algorithm Hash table runtime complexity (insert, search and delete) matrix multiplication algorithm time complexity how to calculate binary search complexity What are the time complexities of various data structures? Complexities of binary tree traversals Time complexity of Euclid's Algorithm What does O(log n) mean exactly?

Examples related to graph-theory

Why is the time complexity of both DFS and BFS O( V + E ) Find all paths between two graph nodes When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)? Difference between hamiltonian path and euler path How to draw a graph in LaTeX? When should I use Kruskal as opposed to Prim (and vice versa)? Find the paths between two given nodes? Finding all cycles in a directed graph Cycles in an Undirected Graph Best algorithm for detecting cycles in a directed graph Why is the time complexity of both DFS and BFS O( V + E ) Find all paths between two graph nodes How to trace the path in a Breadth-First Search? How does a Breadth-First Search work when looking for Shortest Path? How do implement a breadth first traversal? When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)? Performing Breadth First Search recursively Breadth First Vs Depth First