Lecture 4: Solving Recurrences

L4 Annotated Slides PDF

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.