## Lecture 4: Solving Recurrences

We used induction to prove upper (big-Oh) bounds on recurrences; we then introduced the Masters theorem for quick work of special forms of recurrences.

- Induction proof for \( 3T(n/2) + 9n \)
- Same proof for real-world base-case
- What if we skip \( -16n \) ?
- Cookbook/Masters theorem
- Proof of Case 1
- Examples