If software engineering is a craft, algorithms are its grammar. They're the building blocks behind every search bar, every recommendation, every route planner. This post is a tour of the world: what an algorithm even is, how we measure whether one is "good," and the handful of design strategies that turn out to cover almost everything.
What is an algorithm?
An algorithm is a finite, well-defined sequence of steps for solving a problem. The word predates computers by about a thousand years — it comes from the 9th-century Persian mathematician al-Khwārizmī, whose name was Latinised into algorismus.
A good algorithm needs to be:
- Correct. It produces the right answer for every valid input.
- Finite. It terminates after a bounded number of steps.
- Definite. Each step is unambiguous.
- Effective. Each step can actually be carried out.
Once you have correctness, two other dimensions become interesting: efficiency and simplicity. An algorithm that gives the right answer in a year isn't useful; neither is one whose implementation only its author can read.
Measuring efficiency
We care about two resources:
- Time efficiency — how long the algorithm takes as the input grows.
- Space efficiency — how much memory it consumes.
In practice, time tends to be the headline metric. Memory matters, but you can usually buy more RAM more easily than you can buy more wall-clock time.
The first instinct is to time the algorithm with a stopwatch. The problem is that runtimes depend on the machine, the compiler, what else is running, the size of the input — basically everything except the algorithm itself. So we measure something more abstract: how the runtime grows with input size.
Big-O notation
Big-O is the language we use for that. It describes the upper bound on growth. O(n) means "as the input doubles, the work roughly doubles." O(n²) means "as the input doubles, the work roughly quadruples."
| Notation | Name | Example |
|---|---|---|
O(1) | Constant | Looking up a value in a hash map |
O(log n) | Logarithmic | Binary search |
O(n) | Linear | A single pass through a list |
O(n log n) | Linearithmic | Merge sort, quick sort (avg) |
O(n²) | Quadratic | Bubble sort, selection sort |
O(2ⁿ) | Exponential | Naïve recursion on subsets |
O(n!) | Factorial | Brute-force permutations |
Design techniques
Most algorithms you'll meet are instances of one of five general strategies. Knowing the strategy is more valuable than memorising any specific algorithm — it lets you recognise the shape of a new problem.
Brute Force
Try everything. It's almost always the first algorithm you can write for a problem, which makes it useful as a baseline.
Examples: Bubble Sort, Selection Sort, Breadth-First Search, Depth-First Search.
1Bubble Sort, in plain words:
2 walk through the list
3 compare each pair of neighbours
4 swap if they're out of order
5 repeat until you make a full pass without swapping
Time: O(n²). Space: O(1). Wins on simplicity and on tiny inputs; loses on everything else.
Divide & Conquer
Split the problem into smaller pieces of the same shape, solve each piece, then combine the results.
Examples: Merge Sort, Quick Sort, binary tree traversals, the Fast Fourier Transform.
1Merge Sort:
2 if the list has 0 or 1 items, it's already sorted
3 otherwise:
4 split it in half
5 sort each half (recursively)
6 merge the two sorted halves
Time: O(n log n). Space: O(n) for the merge buffer.
The key insight is the recurrence relation: T(n) = 2·T(n/2) + O(n). The "split" is linear in the size of the input, and you do it log n times.
Transform & Conquer
Rearrange the input into a form that makes the answer easier to extract.
Example: Heapsort.
1Heapsort:
2 turn the array into a max-heap (transform)
3 repeatedly take the top of the heap and put it at the end (conquer)
Building the heap is O(n); extracting n elements is O(n log n). The whole thing is O(n log n) with O(1) extra space.
Dynamic Programming
When a problem has overlapping sub-problems, solve each one once and remember the result.
Classic example: the Coin Row Problem. Given a row of coins, pick coins to maximise total value without picking two adjacent ones.
Let F(n) be the best total achievable using the first n coins:
1F(0) = 0
2F(1) = value of coin 1
3F(n) = max( F(n - 1), // skip coin n
4 F(n - 2) + value(n) ) // take coin n
The naïve recursive version is O(2ⁿ) — it re-solves the same sub-problems over and over. Memoising the results brings it down to O(n).
Greedy
At every step, take the choice that looks best right now and never look back. Greedy algorithms are dangerous — they're fast, but only correct when the problem has the right structure.
Example: Prim's Algorithm for the minimum spanning tree of a graph.
1Prim's:
2 start with any vertex in the tree
3 repeatedly add the cheapest edge that connects a tree vertex to a non-tree vertex
4 stop when every vertex is in the tree
It works because of a structural property called the cut property: the minimum-weight edge crossing any cut is in some MST.
When greedy works, it's usually unbeatable on simplicity and speed. The trap is using it on a problem where it doesn't apply — like the classic "make change with fewest coins" problem, which is greedy-correct for US currency but not for arbitrary denominations.
Putting it all together
Most real-world algorithms are mixtures.
- Quicksort is divide-and-conquer, but its pivot selection is greedy.
- Dijkstra's algorithm is greedy, but it depends on a priority queue (a transformed data structure).
- Linear programming relaxations turn integer problems into easier continuous problems (transform), solve those (greedy / specialised), then round back.
The mental model worth carrying:
- Understand the problem. What's the input? What's a valid output? What's the size in practice?
- Find a brute-force solution. Even a slow one — it confirms you understand the problem.
- Look for structure. Overlapping subproblems? Optimal substructure? A natural way to split?
- Pick a strategy. Divide & Conquer, DP, Greedy, Transform.
- Analyse. What's the Big-O? Is it good enough for your real inputs?
- Implement, test, measure.
Wrap-up
Algorithms aren't a fixed library you memorise — they're a way of looking at problems. Every problem you encounter has a shape; the shape suggests a strategy; the strategy suggests an implementation. Knowing the five techniques means that when you see a new problem, your first thought isn't "I have no idea how to solve this," it's "let me figure out which of these shapes this problem has."
That mental shift, more than any specific algorithm, is the prize.