L3 Annotated Slides PDF

We solve recurrences using the tree method, and then use an induction technique to provide a short proof that the solution is correct. We studied Karatsuba and Mergesort as examples.

• Exercise on Change-of-base with logarithms (1m)
• Karatsuba Analysis: Tree (14m)
• Induction O(n^1.6) bound (7m)
• Mergesort Example with Induction (7m)
• Karatsuba, tighter Induction argument (4m)

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