Master Method (4)
Michael L. Littman
September 8th, 1998
ANNOUNCEMENTS
A NORMAL FORM
Putting Bounds in Simplest Form
Addition Rule
Multiplication Rule
More Rules
Summary
SENSE OF SCALE
Preview
How They Scale
Heavy Hitters
Superlinear
Linear
Zooming In
Superlog
Log and Below
SOLVING RECURRENCES
The Substitution Method
Making Good Guesses
The Iteration Method
Terminating the Iteration
The Table Method
Recursion Tree
Summary
CATALOG OF RECURRENCES
Introduction
Linear
Log
Quadratic
Exponential
N Log N
MASTER METHOD
Basic Idea
The Master Tree
The Theorem
Justification
The Gaps
Examples
Next:
ANNOUNCEMENTS
