Overview
This reference consolidates the time and space complexity of every major algorithm covered in this course, organized by paradigm, so you can look up or recall the right numbers quickly during review or before an interview. Complexities are stated using standard variables: n for array/string length, V and E for vertices and edges in a graph, k for a target count or capacity, and W for a weight/capacity bound in pseudo-polynomial cases.
Cricket analogy: A cricket analyst keeps a single reference card of run rates, strike rates, and economy figures for every format, so during a live match he can instantly recall a bowler's economy against pace without recalculating from scratch.
Sorting and Divide-and-Conquer
- Merge sort: O(n log n) time, O(n) space (not in-place, due to auxiliary merge arrays).
- Quickselect (k-th order statistic): O(n) average time, O(n^2) worst case, O(1) extra space (in-place partitioning).
- Closest pair of points: O(n log n) time using a divide-and-conquer sweep with a sorted strip check, O(n) space.
- General divide-and-conquer recurrence T(n) = aT(n/b) + O(n^d) is solved with the Master Theorem.
Greedy Algorithms
- Activity selection: O(n log n) time (dominated by sorting by finish time), O(1) extra space beyond sorting.
- Huffman coding: O(n log n) time using a min-heap of n symbols, O(n) space for the heap and resulting tree.
- Fractional knapsack: O(n log n) time (sort by value-to-weight ratio), O(1) extra space.
Dynamic Programming
- 0/1 knapsack: O(n * W) time and space (pseudo-polynomial in capacity W), reducible to O(W) space with a rolling array.
- Longest common subsequence: O(n * m) time and space for two strings of length n and m.
- Coin change (minimum coins): O(n * amount) time, O(amount) space.
- Longest increasing subsequence: O(n^2) with simple DP, O(n log n) with binary search over tails.
- Matrix chain multiplication: O(n^3) time, O(n^2) space for the DP table over n matrices.
- Edit distance: O(n * m) time and space for two strings of length n and m.
- Subset sum: O(n * target) time and space, pseudo-polynomial in the target value.
Backtracking and String Algorithms
- N-Queens: O(N!) worst case time without pruning, substantially reduced in practice by constraint propagation; O(N) space for the recursion stack.
- Sudoku solver: exponential worst case, bounded in practice by constraint propagation and pruning.
- Permutations/combinations generation: O(n!) time for all permutations, O(2^n) time for all subsets.
- Naive string matching: O(n * m) time comparing pattern of length m against text of length n.
- KMP string matching: O(n + m) time using a precomputed failure function, O(m) space.
- Rabin-Karp: O(n + m) average time using rolling hashes, O(n * m) worst case with hash collisions.
- Trie operations (insert/search): O(L) time per word of length L, O(alphabet_size * total_characters) space worst case.
Graph Algorithms
- BFS / DFS: O(V + E) time, O(V) space for the visited set and queue/stack.
- Union-Find (with path compression and union by rank): nearly O(1) amortized per operation (formally O(alpha(n)), the inverse Ackermann function).
- Dijkstra's algorithm (with a binary heap): O((V + E) log V) time, O(V) space; requires non-negative weights.
- Bellman-Ford: O(V * E) time, O(V) space; handles negative weights and detects negative cycles.
- Floyd-Warshall (all-pairs shortest paths): O(V^3) time, O(V^2) space.
- Basic network flow (Ford-Fulkerson with BFS, i.e. Edmonds-Karp): O(V * E^2) time.
Quick Reference
- Merge sort: O(n log n) time, O(n) space.
- 0/1 knapsack: O(n * W) time and space.
- Longest common subsequence / edit distance: O(n * m) time and space.
- BFS/DFS: O(V + E) time, O(V) space.
- Dijkstra: O((V + E) log V) time with a binary heap; non-negative weights only.
- Bellman-Ford: O(V * E) time; handles negative weights.
- Floyd-Warshall: O(V^3) time, O(V^2) space, all-pairs shortest paths.
- KMP string matching: O(n + m) time, O(m) space.
- Union-Find with path compression: nearly O(1) amortized per operation.
- Quickselect: O(n) average, O(n^2) worst case.
- N-Queens / Sudoku / permutations: exponential/factorial worst case, pruned in practice.
- Activity selection / Huffman / fractional knapsack: O(n log n) time, dominated by sorting or heap operations.
Key Takeaways
- Pseudo-polynomial DP complexities (like O(n*W) for knapsack) depend on the magnitude of numeric inputs, not just count, so they can be slow for large weights/amounts despite looking polynomial.
- Graph algorithm choice depends on weight properties: non-negative -> Dijkstra, possible negative -> Bellman-Ford, all-pairs -> Floyd-Warshall.
- Backtracking worst-case complexities are exponential/factorial, but real-world pruning makes them practical for many inputs.
- Always double-check whether a stated complexity is average-case, amortized, or worst-case before relying on it.
Practice what you learned
1. What is the time and space complexity of the standard 0/1 knapsack dynamic programming solution with n items and capacity W?
2. Which shortest-path algorithm should be used when a graph may contain negative edge weights?
3. What is the time complexity of KMP string matching for a text of length n and pattern of length m?
4. What is the amortized time complexity per operation for Union-Find with both path compression and union by rank?
5. What is the worst-case time complexity of Floyd-Warshall for computing all-pairs shortest paths on a graph with V vertices?
Was this page helpful?
You May Also Like
Algorithm Analysis and Complexity
Learn Big-O, Big-Omega, and Big-Theta notation to analyze and compare the time and space efficiency of algorithms.
The Master Theorem
Apply the Master Theorem's three cases to quickly solve divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n).
Choosing the Right Algorithmic Approach
A decision framework mapping problem characteristics to the correct algorithmic paradigm.