Learning algorithms through analogy. Work in progress.
This isn't a textbook. It's a study journal built through conversation — learning Big O, data structures, and complexity by mapping them onto things that already make sense: medieval warfare, battlefield logistics, armor, terrain.
The approach: if you already think in systems (military, security, infrastructure), you already think algorithmically. You just don't have the vocabulary yet. This guide bridges the gap.
Status: actively studying. Updated as I learn.
- Big O Notation — The Weight of Armor
- Data Structures — Battlefield Formations
- Sorting — Organizing the Line
- Search — Finding the Enemy
- Space Complexity — What the Knight Carries
- Survivorship Bias → Complexity Attacks
- Glossary
Big O answers one question: as the problem gets bigger, how much slower does the solution get?
Think of it as armor weight. A knight can carry 60 pounds of plate and still fight. Give him 600 pounds and he can't move. The armor didn't change — the amount did. Big O measures how the weight scales.
| Big O | Name | Battlefield Analogy |
|---|---|---|
| O(1) | Constant | Drawing your sword. Doesn't matter if there are 10 or 10,000 enemies — the draw takes the same time. |
| O(log n) | Logarithmic | A scout halving the search area each time. "Are they north or south? North. East or west? East." Each question eliminates half the terrain. |
| O(n) | Linear | Inspecting every soldier in the line, one by one. 100 soldiers = 100 inspections. 10,000 = 10,000. Scales directly. |
| O(n log n) | Linearithmic | Splitting your army into squads, sorting each squad, then merging them back. This is how good sorting works (mergesort). |
| O(n²) | Quadratic | Every soldier shakes hands with every other soldier. 10 soldiers = 90 handshakes. 100 soldiers = 9,900. This is where things collapse. |
| O(2ⁿ) | Exponential | Every possible combination of soldiers for a mission. 10 soldiers = 1,024 combinations. 20 soldiers = over a million. 50 = more than atoms in the universe. |
The key insight: O(n²) is the cliff. Everything above it works. Everything below it breaks at scale. When someone says "this algorithm doesn't scale," they usually mean it's O(n²) or worse.
SAPI plates analogy: Your SAPI plate (Small Arms Protective Insert) weighs the same whether you're running 100 meters or 10 miles. That's O(1) — constant. But the fatigue of carrying it scales with distance. The plate is constant; the mission is the variable.
A data structure is how you organize your troops. The formation determines what you can do quickly and what costs you.
Soldiers standing shoulder to shoulder. You can reach any soldier by position number instantly (O(1) access). But inserting someone in the middle means everyone after them shifts down one spot (O(n) insert). Good for: roll call, direct access. Bad for: frequent reorganization.
Each soldier knows only the person next to them. To find soldier #47, you start at #1 and follow the chain (O(n) search). But inserting or removing someone is instant — just redirect who points to whom (O(1) insert/delete if you're already there). Good for: queues, playlists, anything that grows and shrinks. Bad for: "find me the 500th person."
Last in, first out. The last round loaded is the first one fired. You can only see the top. Push a round on, pop a round off. That's it. Simple, fast, constrained by design.
Real use: your browser's back button is a stack. Every page you visit gets pushed on. Back pops the last one off.
First in, first out. The soldier who arrived first eats first. Enqueue at the back, dequeue from the front.
Real use: print jobs, network packets, any system where fairness matters.
Pins on a map. Each pin has a label (key) and a location (value). You don't search the whole map — you go straight to the label. O(1) average lookup. The magic trick of computer science.
The catch: sometimes two labels hash to the same spot (collision). How you handle collisions determines whether your O(1) holds or degrades.
A general at the top, with lieutenants below, with sergeants below them, with soldiers at the bottom. To find anyone, you start at the top and make decisions at each level: "left or right?" A balanced tree gives you O(log n) search — same as the scout halving the terrain.
An unbalanced tree is a chain of command where everyone only has one subordinate — it's just a linked list wearing a tree costume. Balancing matters.
You have 1,000 soldiers and need them sorted by height for formation. How?
Compare neighbors. If they're out of order, swap them. Repeat until no swaps needed. Every soldier compares with every other soldier eventually. O(n²). Never use this for anything real. It exists so you can understand why better algorithms matter.
Split the army in half. Sort each half. Merge the two sorted halves. Repeat recursively. O(n log n). This is what real systems use. The "split, solve, merge" pattern shows up everywhere.
Choose a soldier (the pivot). Everyone shorter goes left, everyone taller goes right. Recurse on each side. Average case O(n log n), worst case O(n²) if you pick bad pivots. Fast in practice because of cache behavior.
Check every position. O(n). Works on anything but doesn't scale.
Requires sorted data. Look at the middle. Too high? Eliminate the top half. Too low? Eliminate the bottom half. Repeat. O(log n). Every step cuts the problem in half.
One-way road analogy: if the addresses on a one-way road are sorted, you don't drive the whole road — you jump to the middle and decide which direction to continue. But if the road isn't sorted (addresses are random), binary search is useless. The precondition matters.
Time complexity is how long it takes. Space complexity is how much gear you need.
A knight in full plate armor with a lance, sword, shield, horse, and squire takes up a lot of space — both physical and logistical. A scout with a knife and a map takes almost none.
| Space | Analogy |
|---|---|
| O(1) | Scout with a knife. Same gear regardless of mission size. |
| O(n) | One supply pack per soldier. Army doubles, supplies double. |
| O(n²) | A communication map between every pair of soldiers. 10 soldiers = 45 connections. 1,000 = ~500,000. |
The tradeoff is real: sometimes you trade space for time. A hash table uses more memory (space) to give you faster lookups (time). A sorted array uses less memory but requires O(log n) search instead of O(1). Every algorithm is a negotiation between time and space.
During WWII, analysts studied bombers that returned from missions and found bullet holes clustered in certain areas. The initial recommendation: armor those areas. Abraham Wald saw the error — the planes that didn't return were hit in the areas with no holes on the survivors. The missing data was the signal.
The algorithmic parallel: when you test an algorithm's performance, you typically test it on inputs that work. The average case. The inputs that "come back." But an attacker doesn't send average inputs. An attacker crafts worst-case inputs — the ones that exploit the algorithm's blind spots.
This is an algorithmic complexity attack. You don't break the algorithm. You feed it inputs specifically designed to trigger its worst-case behavior.
- Hash tables degrade from O(1) to O(n) if you craft inputs that all hash to the same bucket.
- Quicksort degrades from O(n log n) to O(n²) if you feed it pre-sorted data with a bad pivot strategy.
- Regular expression engines can be forced into catastrophic backtracking (ReDoS) with crafted input strings.
The connection to JIT security: JIT compilers (Just-In-Time) optimize code at runtime based on observed patterns. An attacker who understands the JIT's optimization heuristics can craft inputs that trigger specific compilation paths — essentially using the JIT's own optimization logic as an attack surface. The JIT "survives" on normal inputs. The attacker sends the inputs that normal testing never generates.
The bombers that didn't come back are the test cases that didn't get written.
| Term | Plain English |
|---|---|
| Algorithm | A set of steps to solve a problem. A recipe. |
| Big O | How the cost of an algorithm scales as input grows. |
| Time complexity | How long it takes. |
| Space complexity | How much memory it uses. |
| Constant — O(1) | Same cost regardless of size. |
| Logarithmic — O(log n) | Cost grows slowly. Halving each step. |
| Linear — O(n) | Cost grows directly with size. |
| Quadratic — O(n²) | Cost grows with the square of size. The cliff. |
| Exponential — O(2ⁿ) | Cost doubles with each additional element. Unusable at scale. |
| Hash | A function that converts a key into a position. Fast but lossy. |
| Collision | Two keys hash to the same position. Must be handled. |
| Recursion | A function that calls itself with a smaller problem. |
| Divide and conquer | Split the problem, solve the pieces, combine the results. |
| Worst case | The input that makes the algorithm perform its absolute worst. |
| Average case | Expected performance across typical inputs. |
| Amortized | Average cost per operation over a sequence of operations. |
This guide was built through conversation between Nick Kloster and Claude (NuClide). The metaphors came from Nick's background in infantry — the formalizations came from working through them together. The survivorship bias → complexity attack connection was Nick's original insight.
Work in progress. New sections added as studied.
MIT