Algorithms Illuminated (Part 1) The Basics (Tim Roughgarden)（Z-Library）

# Algorithms Illuminated (Part 1): The Basics — Reading Guide ## 【One-Line Pitch】 A friendly, intuition-first introduction to the core ideas of algorithm analysis—big-O notation, divide-and-conquer, and sorting—written for programmers who want to think clearly about performance without drowning in mathematical formalism. Ideal for self-taught developers, interview prep candidates, and CS students who want the "expert tutor" experience on paper. --- ## 【Book Arc】 - **Opening (~0%–10%)**: Sets up what algorithms are, why they matter, and introduces the integer multiplication problem as a gateway—showing that even grade-school algorithms can be improved upon. Establishes the book's signature pattern: define a problem, then explore algorithms for it. - **Early (~10%–23%)**: Introduces Karatsuba multiplication (a clever recursive trick that beats the naive approach) and then moves into MergeSort, the first full divide-and-conquer algorithm. The Merge subroutine is explained step-by-step, and the recursion tree method is introduced for analyzing recursive running times. - **Early–Middle (~23%–32%)**: Completes the MergeSort analysis, proving its O(n log n) running time. Distills three guiding principles for algorithm analysis: worst-case analysis, big-picture thinking (ignoring constants), and asymptotic analysis (focusing on large inputs). - **Middle (~32%–48%)**: Dives into the formal mathematics of asymptotic notation. Big-O is defined rigorously (with the c and n₀ game), and worked examples show how to prove that polynomials are O(n^k), that adding constants to exponents doesn't change growth rates, and how to reason about nested loops and multiple operations. - **Late Middle (~48% onward)**: Additional practice problems and more advanced examples of asymptotic reasoning, preparing readers for the divide-and-conquer algorithms and master method covered later in the book. --- ## 【Key Takeaways】 - **Algorithms are a way of thinking, not just code** (Early): The book repeatedly emphasizes distinguishing between a problem (inputs/outputs) and the algorithm that solves it. This separation is the foundation for all serious algorithm design. - **"Can we do better?" is the algorithm designer's mantra** (Early): Karatsuba multiplication shows that even a "settled" problem like integer multiplication has surprising room for improvement—from four recursive calls down to three, using Gauss's trick. - **Divide-and-conquer is a reusable pattern** (Early): Break a problem into subproblems, solve recursively, combine results. MergeSort is the canonical example, and the Merge subroutine itself is a clean, linear-time operation worth understanding deeply. - **Recursion trees make analysis visual** (Early): Instead of abstract math, the recursion tree method lays out all the work done by recursive calls level by level—making the O(n log n) result for MergeSort feel obvious rather than magical. - **Big-O notation is a modeling choice, not a law of nature** (Middle): It deliberately ignores constant factors and lower-order terms to focus on how performance scales with input size. This "sweet spot" of granularity preserves predictive power while staying mathematically tractable. - **Worst-case analysis keeps algorithms honest** (Middle): By assuming no special properties of the input, worst-case analysis produces general-purpose algorithms that work reliably—even if the average case might be better. - **The formal definition of big-O is a game** (Middle): You pick constants c and n₀, your opponent picks a large n, and you win if T(n) ≤ c·f(n) holds. This game-theoretic framing makes the definition concrete and testable. - **Asymptotic analysis is biased toward large inputs** (Middle): Small inputs don't need algorithmic ingenuity—the interesting questions about performance only emerge when n grows large. --- ## 【Reading Tips】 - **Skim the quiz solutions if you're confident**: The quizzes are well-designed checkpoints, but if you can answer them mentally, the solutions add little. Use them as self-tests rather than reading material. - **Deep-read the MergeSort analysis (Chunk 7–8)**: This is where the book's teaching style shines. The Merge subroutine pseudocode and the recursion tree proof are worth studying line by line—they build intuition you'll reuse for every divide-and-conquer algorithm later. - **Treat the big-O formal definition (Chunk 14) as a workout**: The game-theoretic framing (you vs. an opponent choosing n) is the clearest way to internalize what big-O really means. Work through the polynomial example yourself before reading the proof. - **Skip the additional examples in Section 2.5 if pressed for time**: The book itself says these are optional practice. Return to them if you want to sharpen your proof skills, but they don't introduce new concepts. - **Don't skip the "Word of Caution" about constants**: The warning that c and n₀ cannot depend on n is the most common source of confusion in asymptotic proofs. Read it twice. --- ## 【Coverage Limits】 This guide covers the opening chapters through the asymptotic notation material (roughly the first half of the book). The excerpts do not cover the master method, randomized algorithms, or the selection algorithms promised in the preface—those appear later in Part 1. --- ##