Beyond the language. An introduction to algorithms.
summary
Compares concrete algorithms for finding a heavier poisoned doughnut using a scale as computation model then measures costs: checking one-by-one is O(n), pairwise still O(n) (half the comparisons), divide-in-two is O(log n) and divide-in-three is log base 3 so faster — with 10,000 items the divide-by-2 strategy takes ~13 minutes versus ~3.5 days for the naive pairwise and ~6 days for plain linear. Shows Ruby VM hash internals: 16-bucket array, max bucket density = 5, and a benchmark where forcing all keys to hash to 3 causes lookups to degrade from near-constant to linear — the experiment works.
AI-written summary · about
chapters (14)
- 0:00Introduction to algorithms
- 2:31About the speaker
- 3:14What is an algorithm
- 5:44The poisoned beignet problem
- 7:18Measuring algorithm efficiency
- 10:09Big O notation explained
- 14:34Analyzing the first algorithm
- 15:40Pairwise comparison approach
- 17:05Divide and conquer method
- 19:14Three-group splitting strategy
- 21:44Language vs algorithm performance
- 23:33Ruby hash tables deep dive
- 31:25Why the last key performs well
- 31:45Do you need algorithms to program?
