Search, graph, and tree algorithm complexity

Algorithm complexity

A quick reference for the searching, graph, heap, and interval algorithms that come up most in interviews. Detailed breakdowns follow in the next section.

Algorithm	Best	Average	Worst	Space
Linear search	`O(1)`	`O(n)`	`O(n)`	`O(1)`
Binary search	`O(1)`	`O(log n)`	`O(log n)`*	`O(1)`*
BFS	`O(V + E)`	`O(V + E)`	`O(V + E)`	`O(V)`
DFS	`O(V + E)`	`O(V + E)`	`O(V + E)`	`O(V)`*
Heap insert	`—`	`O(log n)`	`O(log n)`	`O(1)` auxiliary
Heap peek	`O(1)`	`O(1)`	`O(1)`	`O(1)`
Heap extract min or max	`—`	`O(log n)`	`O(log n)`	`O(1)` auxiliary
Merge intervals	`—`	`O(n log n)`	`O(n log n)`	`O(n)`*
Union-Find operation	`—`	`Amortized O(α(n))`	`—`	`O(n)` total structure
Dijkstra with binary heap	`—`	`—`	`O((V + E) log V)`*	`O(V + E)`

* Complexity depends on the implementation and assumptions. Binary search takes O(log n) time only on sorted random-access data; iterative binary search uses O(1) auxiliary space. BFS and DFS space depends on the graph representation and traversal implementation. Dijkstra's bound assumes a standard adjacency-list implementation with a binary heap.
Heap insert is O(log n) as an upper bound. On random data the expected cost is O(1).
Merge intervals is dominated by sorting the intervals; the O(n) space is the output list, plus any space the sort needs.
Union-Find reaches amortized O(α(n)) only with path compression and union by rank or size. α is the inverse Ackermann function, which stays below 5 for any input that fits in memory.

Graph and tree algorithms

V is the number of vertices, E the number of edges, n the number of tree nodes, and h the tree height (about log n when balanced, up to n when skewed). Graph bounds assume an adjacency list unless noted.

Traversal and search

Algorithm	Time	Space	Notes
Breadth-first search (BFS)	`O(V + E)`	`O(V)`	Uses a queue. Finds shortest paths by edge count. O(V²) with an adjacency matrix.
Depth-first search (DFS)	`O(V + E)`	`O(V)`	Uses recursion or an explicit stack, so depth can reach V. Basis for cycle detection and topological sort. O(V²) with an adjacency matrix.
Binary search on a sorted array	`O(log n)`	`O(1)` iterative, `O(log n)` recursive	Requires sorted, random-access data. Also works on any monotonic yes/no condition, not just arrays.
Binary search tree lookup	`O(h)`	`O(1)` iterative	O(log n) when balanced, O(n) when skewed.
Preorder, inorder, postorder traversal	`O(n)`	`O(h)`	Recursion or stack depth is the height. Inorder on a binary search tree visits keys in sorted order.
Level-order traversal	`O(n)`	`O(w)`	Uses a queue; w is the widest level, which can be about n/2 in a complete tree.
Morris traversal	`O(n)`	`O(1)`	Inorder or preorder with no stack. Temporarily rewires tree pointers, so it is not safe for concurrent readers.

Heap operations

For a binary heap holding n items.

Operation	Time	Notes
Peek min or max	`O(1)`	Read the root.
Insert	`O(log n)`	Append at the end, then sift up. O(1) on average for random data.
Extract min or max	`O(log n)`	Swap the root with the last item, remove it, then sift down.
Build heap from an array	`O(n)`	Sift down from the last parent to the root. Faster than n separate inserts, which cost O(n log n).
Change priority or delete at a known index	`O(log n)`	Finding the index without a position map costs O(n).
Search for an arbitrary value	`O(n)`	A heap only orders parents against children.
Heapsort	`O(n log n)`	O(1) extra space. See the sorting table.

Shortest-path algorithms

Algorithm	Edge weights	Time	Space	Notes
BFS	Unweighted	`O(V + E)`	`O(V)`	Single source.
0-1 BFS	0 or 1 only	`O(V + E)`	`O(V)`	Single source. Uses a deque instead of a heap.
Shortest path in a DAG	Any, including negative	`O(V + E)`	`O(V)`	Single source. Relax edges in topological order.
Dijkstra with binary heap	Non-negative	`O((V + E) log V)`	`O(V + E)`*	Single source. The usual choice for sparse graphs.
Dijkstra with array	Non-negative	`O(V²)`	`O(V)`	Single source. Beats the heap version on dense graphs.
Dijkstra with Fibonacci heap	Non-negative	`O(E + V log V)`	`O(V + E)`	Single source. Best bound, rarely fastest in practice.
Bellman–Ford	Negative allowed	`O(V·E)`	`O(V)`	Single source. Detects negative cycles reachable from the source.
Floyd–Warshall	Negative allowed, no negative cycles	`O(V³)`	`O(V²)`	All pairs. Works on an adjacency matrix.

* The space includes the adjacency list. A heap that allows duplicate entries instead of decrease-key can hold up to E items; an indexed heap with decrease-key needs only O(V) beyond the graph. The O((V + E) log V) bound assumes a standard adjacency-list implementation.
Other space figures count extra space beyond the input graph.

Minimum spanning trees

These algorithms take a connected, undirected, weighted graph. On a disconnected graph they produce a minimum spanning forest.

Algorithm	Time	Space	Notes
Kruskal	`O(E log E)`	`O(V + E)`	Sort edges, then add each one that joins two components, using Union-Find. O(E log E) equals O(E log V) because E is at most V². Works from an edge list.
Prim with binary heap	`O(E log V)`	`O(V + E)`	Grows one tree from a start vertex. Good for sparse graphs.
Prim with array	`O(V²)`	`O(V)`	Good for dense graphs stored as a matrix.
Prim with Fibonacci heap	`O(E + V log V)`	`O(V + E)`	Best bound, rarely fastest in practice.
Borůvka	`O(E log V)`	`O(V)`	Each round adds the cheapest edge leaving every component. Components at least halve each round, so it needs at most log V rounds. Easy to parallelize.

Topics on this page

Each one has its own page with an explanation, code, and the mistakes people make.

Binary search
O(log n)
Linear search
O(n); O(1) if the target is first
Breadth-first search (BFS)
O(V + E)
Depth-first search (DFS)
O(V + E)
Tree traversals
O(n)
Dijkstra's algorithm
O((V + E) log V) with a binary heap
Bellman–Ford
O(V · E)
Kruskal's algorithm
O(E log E)
Prim's algorithm
O(E log V) with a binary heap; O(V²) with an array
Merge intervals
O(n log n)

Search and graph algorithms