Space complexity analysis
A queue that holds n elements uses O(n) memory for the items themselves. Algorithm analysis also counts auxiliary space: extra arrays (e.g. visited), the BFS frontier queue, and recursion stack (BFS usually avoids deep recursion).
On this page
- Structural space — array vs linked nodes
- Auxiliary space — BFS, level-order
- Bounds — queue size in graph algorithms
1) Space for the queue structure
| Implementation | Data | Overhead |
|---|---|---|
| Contiguous array | n elements in O(n) slots | O(1) indices (front, rear, size) |
| Singly linked list | n nodes | O(n) next pointers + two head pointers |
| Binary heap | n keys in array | O(1) bookkeeping |
2) Auxiliary space in algorithms
| Algorithm | Queue role | Typical extra space |
|---|---|---|
| BFS (graph) | Holds frontier of vertices | O(V) for queue + visited + adjacency storage |
| Level-order (tree) | Node pointers per level | O(w) where w = max width (≤ n) |
| Unweighted shortest path | Same as BFS | O(V) distance array + O(V) queue (worst) |
3) Why BFS queue is O(V) in the worst case
Before processing the next vertex, the queue may hold many vertices at once (e.g. star graph: center connected to V−1 leaves). So peak queue size is O(V). Total graph storage is separate (often O(V + E) for adjacency lists).
Summary formula
Total space ≈ (space for graph/tree) + (visited / dist arrays) + (BFS queue peak)
= O(V + E) + O(V) + O(V) for adjacency-list BFS on a simple graph
Key takeaway
Separate storage for elements from auxiliary structures. For BFS, always account for visited and the worst-case frontier size.
Next up: Time complexity · BFS using queue · All queue topics