Sonith ManakkatEleven parts in, you have met many algorithms. The skill that remains is choosing: looking at a problem and knowing which family it belongs to. This final part is a cheat sheet. Read the problem as a question, find the question below, and take the good first choices. Each row says why, so you can reason about cases the sheet does not cover.
Ask the question first
- 1Protecting data, or storing passwords?Yes Vetted encryption or slow salted hashing from a trusted libraryNo keep going
- 2Links between things, such as routes?Yes Graph search: BFS, DFS or DijkstraNo keep going
- 3Exact lookups by key, many times?Yes Hash tableNo keep going
- 4Most urgent item first?Yes Heap or priority queueNo keep going
- 5Best answer from repeating subproblems?Yes Dynamic programmingNo keep going
- 6Just need items in order?Yes The built-in sortNo keep going
- 7OtherwiseLinear search or the simplest code, then measure
Takeaway. Name the job first, then pick the family that matches it.
- What is the job?Find, order, relate, choose, rank, learn or protect
- How big is the data?Ten items or ten million changes the answer
- What matters most?Speed, memory, simplicity or predictability
- Is there a library?A tested built-in usually beats your own
The cheat sheet: finding things
| Question | Good first choices | Why |
|---|---|---|
| Find in a small or unsorted list | Linear search | Nothing to prepare, and cheap when the list is short |
| Find in sorted data, many lookups | Binary search, or a hash table | Binary search takes about log n steps; hashing is fast on average |
| Find by exact key | Hash table | Average constant-time lookup, no order needed |
| Find by range, or walk in order | Balanced tree, or sorted array | Keeps order, so ranges and neighbours are easy |
A quick way to read the rows above: if the data is small, almost anything works, so pick the simplest. If you will look things up many times, pay once to organise the data (sort it, or build a hash table) and then enjoy fast lookups. Organising costs time up front and memory, so it only pays off when the number of lookups is large.
Expert viewTrade-offs behind the lookup choices
Hash tables give constant-time lookups on average, but they have no order and their worst case is worse when many keys collide. Binary search needs sorted data held in an indexable form, and inserting into a sorted array is costly, which is why dynamic data often uses a balanced tree, giving about log n time for lookup, insertion and in-order walks. The right choice depends on the mix of operations: mostly reads, mostly writes, or range queries.
Putting things in order
| Question | Good first choices | Why |
|---|---|---|
| Just need it sorted | Your language's built-in sort | Well tested and tuned; many libraries use hybrids of the classic ideas |
| Tiny or nearly sorted data | Insertion sort | Very little overhead, close to linear on nearly sorted input |
| Equal items must keep their order | Merge sort (a stable sort) | Stable, with steady n log n time, at the cost of extra memory |
| Memory tight, good average speed | Quick-style sort | In place and fast on average, but not stable and has a bad worst case |
Relationships, choices and priorities
| Question | Good first choices | Why |
|---|---|---|
| Network: fewest steps | BFS | Explores level by level, so the first arrival uses the fewest steps |
| Network: visit or explore all | DFS | Goes deep, simple and low in memory |
| Network: cheapest weighted route | Dijkstra (A* with estimates) | Finds least cost when costs are not negative; estimates focus the search |
| Best answer, greedy choice is provably safe | Greedy | Fast and simple when the proof holds |
| Best answer, overlapping subproblems | Dynamic programming | Solve each small case once and reuse it |
| Best answer, otherwise | Backtracking with pruning | Try options, abandon dead ends early |
| Most urgent first | Heap, or priority queue | Always gives the best item quickly as items arrive |
Expert viewGreedy needs a proof
A greedy method makes the best-looking choice at each step. It is only correct when the problem has a property that makes this safe, and that has to be shown, not hoped for. Coin change shows the danger: with coins of 1, 3 and 4, a greedy pick for 6 gives 4+1+1 (three coins) while 3+3 needs two. When the greedy choice cannot be justified and subproblems repeat, dynamic programming is the dependable route. Where neither fits, search with pruning is the fallback, and it may be exponential in the worst case.
Ranking, learning and protecting
Notice how these rows differ from the earlier ones: here the right answer depends on data and context more than on a fixed recipe, so measure the outcome and not only the speed.
| Question | Good first choices | Why |
|---|---|---|
| Recommend or rank | Scoring and similarity | Give items a score from signals, then sort by it |
| Learn from data | Machine learning | Patterns are learned from examples when rules are hard to write |
| Protect data | Vetted encryption libraries | Never write your own cryptography |
| Fingerprint or compare data | Hashing | Short, fixed-size, changes if the data changes |
| Store passwords | Slow, salted hashes from a trusted library | Passwords are never kept, only checked |
The series at a glance
| Part | Core idea | Reach for it when |
|---|---|---|
| Big-O | Describing how work grows | Comparing options before building |
| Sorting | Putting items in order | You need order or want faster lookups |
| Searching | Finding items | A list or collection must be queried |
| Hashing | Key to location, and fingerprints | Fast lookup by key, or detecting change |
| Graphs | Things and their links | Routes, networks, dependencies |
| Recursion and dynamic programming | Small cases reused | Subproblems repeat |
| Greedy, divide and conquer, backtracking | Three strategies | Designing a new method |
| Trees and heaps | Ordered or prioritised structures | Ranges, hierarchies, most-urgent-first |
| Ranking and recommendations | Scores and similarity | Ordering results for a person |
| Machine learning | Learning from examples | Rules are too hard to write |
| Encryption | Keys, signatures, hashes | Data must be kept private or verified |
What experts add
- Measure firstTime the real program before changing it
- Clarity firstCode people can read is code people can fix
- Use librariesThey are tested and tuned by many people
- Data size decidesSmall inputs hide poor choices
Expert viewMeasure, profile, and the cost of complexity
Big-O describes how work grows, not how fast a program runs today. A simple O(n squared) method can beat a cleverer O(n log n) one on small inputs because of lower overhead, and memory, caches and input shape all matter. The standard advice is to profile a realistic workload, find the actual hot spot, change it, and measure again. Every clever structure also has a cost: more code, more bugs and more to explain. Famously, premature optimisation, tuning code before you know where time is spent, wastes effort and often damages clarity for no gain.
The fastest algorithm on paper is always best
Overheads and small inputs mean a simple method can win. Measure real data
Writing my own version shows skill and is safer
Tested library code is usually faster and safer, especially for sorting and security
- 1 (constant)
- log n
- n
- n log n
- n squared
- 2 to the n
Expert viewReading the growth chart
Curves that stay flat or climb gently (constant, log n, n) cope with huge inputs. Curves that bend upward fast (n squared and worse) look harmless at ten items and become impossible at a million. Choosing well often means moving a problem from a steep curve to a gentle one, for example by sorting once and then searching many times, or by using a hash table in place of repeated scans.
Try it by hand: pick the algorithm
Read each scenario, name the question it asks, and choose a first approach. Then check the notes below.
- A. 12 names, find oneUnsorted, searched once
- B. Map of 8 townsFind the route with fewest road changes
- C. A million customer idsLook up a customer by id, again and again
- Check your answersCompare with the notes below
- A: Linear search. Sorting twelve names to look up one costs more than just scanning them.
- B: Breadth-first search, because it finds the fewest steps first. If roads had different costs and the cheapest total mattered, Dijkstra would be the next step up.
- C: A hash table keyed by customer id. If you also needed customers in id order, a balanced tree or a sorted array would serve instead.
Name the question, measure the data, and choose the simplest tool that fits.
Frequently asked questions
How do I decide between two algorithms that both fit?
Take the simpler one, and measure on realistic data if speed matters.
Should I always use the lowest Big-O?
No. Big-O describes growth, and small inputs or large overheads can reverse the order.
When should I write my own algorithm?
When a library does not cover your need, or for learning. For sorting and cryptography, use the library.
Is there one algorithm to remember?
No. Remember the questions: find, order, relate, choose, rank, learn, protect.