Basic Idea

Handles recurrences of the form: T(n) = a T(n/b)+f(n). where $a \ge 1$, b > 1, and f(n) is some function.

We gloss over some technicalities:

• T(n) is usually only defined for integer n, so we really need $T(\lceil n/b \rceil)$.
• boundary conditions like T(1) = 0.

This is ok because these details get swallowed up by the big O or big Theta that we are eventually going to wrap around things anyway.