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.

• 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

To view this video please enable JavaScript, and consider upgrading to a web browser that supports HTML5 video