Adventures in the World of (Algorithmic) Complexity
summary
Covers practical use of Big O notation with concrete examples: compares two bracket‑balance algorithms (one backtracking, one single counter) and explains why the counter is better for time. Shows a real bug from generating 10,000 four-digit PINs until collisions exhaust the space, and designs a URL shortener that avoids storing 33 million combinations by pre‑shuffling character wheels so issuance is O(1) time with linear space — solution and tradeoffs are explicit.
AI-written summary · about
chapters (18)
- 0:00Intro
- 1:59An algorithm
- 2:18A problem
- 3:53Solution B
- 6:15Moore's Law
- 6:46Still, difficult problems remain
- 8:25The wheat and the chessboard story
- 11:22Another example: dominoes
- 18:35A useful visualization
- 19:43Most common complexities
- 20:37Constant complexity
- 22:49Linear complexity
- 24:09Quadratic complexity
- 25:10Exponential complexity
- 25:28Logarithmic complexity
- 26:58Complexities: a comparison
- 27:26A thing to remember
- 35:23A hashing solution
