At an input size of one million, an O(log n) algorithm takes about 20 steps. An O(n²) algorithm takes a trillion. No amount of faster hardware, tighter loops or better compiler flags closes that gap — only choosing a different algorithm does.
That is why this list exists, and why every entry below carries its complexity alongside the description. These are ten algorithm families rather than ten individual algorithms, because that is how the knowledge is actually useful: you rarely need to recall Dijkstra’s exact steps, but you do need to recognise a shortest-path problem when one arrives disguised as a business requirement.
Table of Contents
- Complexity at a Glance
- 1. Sorting Algorithms
- 2. Search Algorithms
- 3. Hashing
- 4. Graph Traversal: BFS and DFS
- 5. Shortest Path: Dijkstra and Friends
- 6. Minimum Spanning Trees
- 7. Dynamic Programming
- 8. Divide and Conquer
- 9. Backtracking
- 10. String Matching
- How to Actually Learn These
- Key Takeaways
- Frequently Asked Questions
- Conclusion
Complexity at a Glance
| Family | Typical time | Space | Use when |
|---|---|---|---|
| Sorting (comparison) | O(n log n) | O(1)–O(n) | Data must be ordered, or ordering enables a faster next step |
| Binary search | O(log n) | O(1) | Data is already sorted and you need lookups |
| Hashing | O(1) average | O(n) | You need fast lookup by key and order does not matter |
| Graph traversal (BFS/DFS) | O(V + E) | O(V) | Exploring connections, reachability, shortest unweighted path |
| Shortest path (Dijkstra) | O((V + E) log V) | O(V) | Weighted graph, non-negative edges |
| Minimum spanning tree | O(E log E) | O(V) | Connect everything at minimum total cost |
| Dynamic programming | Problem-specific | O(n)–O(n²) | Overlapping subproblems with optimal substructure |
| Divide and conquer | Often O(n log n) | O(log n) stack | The problem splits cleanly into independent halves |
| Backtracking | Often exponential | O(depth) | Constraint satisfaction with a searchable solution space |
| String matching (KMP) | O(n + m) | O(m) | Repeated pattern search in large text |
Two things this table is not. It is not a substitute for measuring — constants matter, and an O(n²) algorithm on 50 elements will beat an O(n log n) one with a heavy constant factor. And average case is not worst case: hashing is O(1) until every key collides, and quicksort is O(n log n) until the pivot choice degenerates.
1. Sorting Algorithms
Sorting is the most-implemented family in the list, and the one most often reached for unnecessarily — much of its value is as a preprocessing step that makes something else fast. Sorted data enables binary search, makes duplicate detection linear, and turns many range queries into two lookups.
Know these three: quicksort (fast in practice, O(n log n) average, O(n²) worst), merge sort (guaranteed O(n log n), stable, needs O(n) extra space), and one simple quadratic sort such as insertion sort so you understand what the efficient ones improve upon.
In production, call the library sort. std::sort, Arrays.sort and sorted() have absorbed decades of edge cases — introsort switches to heapsort when quicksort’s recursion runs too deep, and Timsort exploits the partial ordering real data usually has.
On-site implementations: the quicksort guide covers Lomuto versus Hoare partitioning with measured swap counts and code in five languages, and shell sort shows the gap-sequence idea that bridges insertion sort and the O(n log n) family.
2. Search Algorithms
Binary search is the one to internalise: O(log n) on sorted data, and the source of an unreasonable number of off-by-one bugs. Jon Bentley’s observation that most programmers cannot write it correctly on the first attempt has held up remarkably well.
Linear search is O(n) and is genuinely the right answer for small or unsorted collections — the cost of sorting first is only worth paying if you will search repeatedly.
The decision rule: search once on unsorted data, use linear. Search repeatedly, sort once then binary search, or build a hash table.
3. Hashing
Hashing trades memory for speed, converting a key into an array index so lookup is O(1) on average rather than O(log n) or O(n). It is the mechanism behind std::unordered_map, Python’s dict, Java’s HashMap, and hash indexes in database systems.
What to actually understand: collisions are inevitable — the pigeonhole principle guarantees it — so the interesting part is how they are resolved (chaining versus open addressing), and what happens to that O(1) guarantee when the load factor climbs or an adversary chooses colliding keys deliberately.
Cryptographic hashes such as SHA-256 solve a different problem — integrity and irreversibility rather than fast lookup — and the two should not be conflated.
4. Graph Traversal: BFS and DFS
Many foundational graph problems start with one of these two traversals.
Breadth-first search explores level by level using a queue, and finds the shortest path in an unweighted graph as a side effect. Depth-first search follows one path to exhaustion using a stack or recursion, and is the basis for cycle detection, topological sorting and connected components.
Both are O(V + E). The choice is about shape: BFS when you want the nearest thing, DFS when you want to know whether a path exists at all or need to explore exhaustively.
5. Shortest Path: Dijkstra and Friends
Dijkstra’s algorithm finds the shortest path in a weighted graph with non-negative edges, in O((V + E) log V) with a binary heap. It is a foundation for route-planning algorithms and is used in link-state routing such as OSPF, as well as many other weighted-graph problems.
The constraint that catches people out: non-negative edges only. With negative weights, Dijkstra’s greedy choice stops being safe and you need Bellman-Ford (O(V·E), slower but tolerates negative edges and detects negative cycles).
6. Minimum Spanning Trees
Given a weighted graph, connect every vertex at the lowest total cost. This is network design in its purest form — laying cable, planning pipelines, or clustering.
Kruskal’s algorithm sorts every edge and greedily accepts any that does not create a cycle, using union-find for the cycle check. Prim’s algorithm grows a single tree outward from a start vertex. Both are greedy, both are correct, and the choice is about input shape: Kruskal for sparse graphs with an edge list, Prim for dense graphs with an adjacency structure.
On-site implementation: the Kruskal’s algorithm guide covers union-find with path compression and union by rank, with a step-by-step trace and code in C and C++.
7. Dynamic Programming
The family that most reliably separates people who have practised from people who have not.
Dynamic programming applies when a problem has overlapping subproblems and optimal substructure — the same smaller problems recur, and an optimal overall answer is built from optimal partial answers. The technique is to solve each subproblem once and store the result, either top-down with memoisation or bottom-up with a table.
Naive recursive Fibonacci is O(2ⁿ); memoised, it is O(n). That single example is the whole idea, and it is worth implementing both to feel the difference.
On-site implementation: the knapsack problem is the canonical DP exercise — maximise value under a weight constraint — and it generalises to resource allocation, budgeting and scheduling.
8. Divide and Conquer
Split the problem into independent subproblems, solve them recursively, combine the results. Merge sort, quicksort, binary search and the fast Fourier transform all follow this shape.
It is worth distinguishing from dynamic programming, since the two are frequently confused: divide and conquer subproblems are independent; dynamic programming subproblems overlap. That difference is exactly why DP needs a memo table and divide and conquer does not.
9. Backtracking
Explore candidate solutions incrementally and abandon a branch as soon as it cannot lead to a valid answer. N-Queens, Sudoku solvers, maze pathfinding and constraint satisfaction all sit here.
Backtracking is typically exponential in the worst case, but pruning — recognising a dead branch early — is what makes it practical. The gap between a naive implementation and a well-pruned one is often the difference between seconds and centuries.
10. String Matching
Finding a pattern inside a larger text. The naive approach is O(n·m); Knuth-Morris-Pratt achieves O(n + m) by precomputing how far it can safely skip after a mismatch, and Rabin-Karp uses a rolling hash, which makes it the natural choice for searching multiple patterns at once.
Most languages give you this in the standard library — std::string::find, str.index, String.indexOf — and for anything involving genuine pattern languages rather than fixed substrings, a regular expression engine has already solved it better than you will.
How to Actually Learn These
Reading about algorithms produces recognition, not recall. The gap closes only through implementation.
- Implement each one once from scratch, without looking at a reference. The bugs you hit are the learning.
- Then read a good implementation and note what it does differently — usually edge cases and constant-factor work you did not think about.
- Practise recognising them in disguise. Interview questions and real requirements rarely say “use Dijkstra”; they say “find the cheapest route”. Competitive programming sites are the fastest way to build that recognition.
- Learn the complexity, not the code. In six months you will not remember KMP’s failure-function construction. You should remember that repeated substring search has an O(n + m) solution, which is enough to find it again.
For algorithm-focused interviews: these families above cover the overwhelming majority of questions asked. Depth on sorting, binary search, hashing, BFS/DFS and dynamic programming is worth more than shallow familiarity with all ten.
Key Takeaways
- Complexity dominates optimisation. At n = 1,000,000, O(log n) is ~20 steps and O(n²) is 10¹². No micro-optimisation crosses that gap.
- Learn families, not instances. Recognising a shortest-path problem matters more than recalling Dijkstra’s pseudocode.
- Average case is not worst case. Hashing is O(1) until it collides; quicksort is O(n log n) until the pivot degenerates.
- Divide and conquer has independent subproblems; dynamic programming has overlapping ones. That single distinction explains why one needs a memo table.
- Dijkstra requires non-negative edges. Negative weights need Bellman-Ford.
- Use the library implementation in production and write your own only to learn.
Frequently Asked Questions
Conclusion
The reason this list is ten families rather than ten algorithms is that the recall you need in practice is not procedural. Nobody writes Dijkstra’s from memory at work; they recognise that a problem is a weighted shortest path, look up the details, and know roughly what it will cost to run. That recognition is the transferable skill, and it is built by implementing things once rather than reading about them repeatedly.
The complexity table is the part worth keeping close. Most performance problems in real systems are not slow code — they are the right code applied at a scale it was never chosen for, and the fix is a different algorithm rather than a faster loop. The algorithms section covers individual implementations in depth as you work through them.
