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:
- Queue: In the worst case (like a complete graph), you might enqueue nearly all vertices before dequeuing any. Maximum size approaches V.
- Visited set/array: You must track which vertices you've seen to avoid cycles—this always takes O(V) space.
- 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.