Solving recurrences The analysis of merge sort from Lecture I required us to solve a recurrence Recurrences are like solving integrals erential equations, etc o Learn a few tricks Lecture 3: Applications of recurrences
The divide-and-conquer design paradigm 1. Divide the problem(instance) into subproblems 2. Conquer the subproblems by solving them recursively 3. Combine subproblem solutions
Quicksort Proposed by C. A.R. Hoare in 1962 Divide-and-conquer algorithm Sorts“ in place”( like insertion sort, but not like merge sort Very practical(with tuning)
