SESKStuff Everyone Should Know
SESK: Stuff Everyone Should Know · sesk.info/tech-bfs-linear-time

Using adjacency lists, what is breadth-first search's running time on a graph?

O(V + E), linear in the number of vertices plus edges.

Start playing free

  1. O(V + E) ✔
  2. O(V × E)
  3. O(log V)

Why: A graph is a set of vertices (points) joined by edges (links). BFS visits each vertex once and looks along each edge a constant number of times, so the work adds up to vertices plus edges.

Huh, didn't know that: In a graph where every edge counts the same, BFS finds the fewest-hops path from the start to every other vertex.

The dad joke
Breadth-first search is how I look for my keys. Every room on this floor before I go upstairs.
Like this card?
Play the game

References

Answer: O(V + E). A graph is a set of vertices (points) joined by edges (links). BFS visits each vertex once and looks along each edge a constant number of times, so the work adds up to vertices plus edges.

  1. MIT 6.006 Introduction to Algorithms, Lecture 9: Breadth-First Search ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_lec9
    So breadth-first search runs in linear time! O(|V | + |E|)
    Checked 2026-10-11.

Think this answer is wrong? Tap "Challenge this answer" on the card in the game and tell us why.

Test yourself in the game

Tech & GadgetsWhat must be true about a list before you can use binary search on it?Tech & GadgetsIn Big O notation, what do you ignore when describing an algorithm's running time?Tech & GadgetsWhat does it mean that a sorting algorithm is stable?

That's stuff everyone should know.