Course contentsShow
← Computer Science
Lesson 698 of 2,87217. Graph Traversal AlgorithmsFree lesson

BFS Time and Space Complexity

Analyzing BFS performance: O(V + E) time complexity, O(V) space for queue and visited set, and memory considerations.

BFS Time and Space Complexity

What you'll learn: You'll understand exactly why BFS takes O(V + E) time and O(V) space, and what this means for memory usage.

The Performance Profile

When you run BFS on a graph with V vertices and E edges, the algorithm visits every vertex once and explores every edge once. This gives us the famous O(V + E) time complexity.

Here's why:

  • You process each vertex exactly once when you dequeue it: O(V)
  • For each vertex, you examine all its outgoing edges to find neighbors: O(E) total across all vertices
  • Combined: O(V + E)

Notice this works for both adjacency lists and adjacency matrices, though the constant factors differ. With a matrix, checking all neighbors means scanning an entire row, making it effectively O(V²) even for sparse graphs.

Space Complexity Breakdown

BFS requires O(V) auxiliary space for three main structures:

  1. Queue: In the worst case (like a complete graph), you might enqueue nearly all vertices before dequeuing any. Maximum size approaches V.
  2. Visited set/array: You must track which vertices you've seen to avoid cycles—this always takes O(V) space.
  3. Parent/distance arrays (optional): If you're tracking shortest paths or reconstructing routes, these also take O(V).

The graph representation itself (adjacency list or matrix) is considered input, not auxiliary space.

Memory Considerations

For dense graphs where E ≈ V², BFS is memory-efficient since its space cost depends on vertices, not edges. For very large graphs, the queue can grow significantly—imagine breadth-first searching a social network where one person has thousands of connections.

Key Takeaway: BFS runs in O(V + E) time because it visits every vertex and explores every edge once, and uses O(V) space for its queue and visited tracking—making it efficient for most practical graph traversal needs.