## Lecture 3: Solving Recurrences

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)