Complexity
Big-O, time-space tradeoffs, and where theory parts from the profiler
01
·Complexity·FREE·7 min read
Complexity From Scratch — What Big-O Actually Measures
What O(n), O(n log n) and O(n²) feel like as wall-clock time. Constant factors versus growth rate, trading time against space, and the three reasons your profiler disagrees with the textbook — assuming no prior knowledge.
02
·Complexity·★ MEMBER·8 min read
When Big-O and Your Benchmarks Disagree — Caches, Branches, and Memory Bandwidth
Two O(n) programs can differ by orders of magnitude in the real world. This article unpacks what Big-O deliberately throws away — cache hierarchies, branch prediction, and memory bandwidth — and how to reason about each.
03
·Complexity·★ MEMBER·12 min read
Randomized Algorithms — Why Rolling Dice Makes Things Faster
Why does adding randomness make an algorithm faster? We build up quicksort with a random pivot, the one-sided error of Bloom filters, and the Monte Carlo / Las Vegas split from zero background — ending with the ways mishandled randomness actually breaks systems in production.
04
·Complexity·FREE·9 min read
NP-Completeness from Scratch — Not Unsolvable, but Fast to Verify
NP does not stand for Non-Polynomial. It is the class of problems where, if someone hands you an answer, you can check it quickly. We build up P vs NP, reductions and NP-completeness from zero, then look at how all of it shows up in shift rosters and delivery routes.
05
·Complexity·★ MEMBER·12 min read
Approximation Algorithms — Trading Exactness for a Guarantee
The craft of giving up on the optimal answer while attaching a price tag that reads "never worse than X times optimal". We build up the approximation ratio, carry a greedy proof all the way to the end, and see why the triangle inequality flips the entire conclusion for the traveling salesman problem.