Lecture 3: Solving Recurrences

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.