TAOCP Vol 1: Fundamental Algorithms · Week 27
TAOCP 1.2.11 Asymptotic Representations: reading guide
Big-O notation done properly, then techniques for getting precise asymptotic estimates: the Euler summation formula, and worked examples of approximating sums and factorial-like quantities.
Time About 8 hours this week
Why it matters
Big-O as most people use it is sloppy. Knuth's version lets you say "this is n lg n plus a smaller term" with real meaning, which matters when you compare two algorithms with the same big-O.
Before you start
- 1.2.10 Analysis of an Algorithm
- Calculus: integrals and Taylor series
How to approach it
Read 1.2.11.1 (O-notation) carefully and do its exercises. Euler's summation formula and the later examples are heavy calculus; read for the ideas and follow one example fully. It is fine to leave the HM exercises for later.
Exercises
Do the exercises on O-notation manipulation; skip most HM ones unless calculus is your thing.
Traps
- Treating O( ) as an equality in both directions. It is one-way.
- Getting bogged down in the Euler-Maclaurin details on a first pass.