This is an old revision of the document!
Table of Contents
Week 7
Chapter Scores
- Readability Score: 7/10
- Interest Score: 4/101)
Readings
Chapter 5: Divide and Conquer
5.1: A First Recurrence - The Mergesort Algorithm
This section of the reading describes mergesort as the most canonical divide-and-conquer algorithm. A divide-and-conquer algorithm is an algorithm that divides the input into multiple pieces (usually 2), solves each subproblem using recursion, and then combines the results of those recursive calls into a solution. As with all recursion, the recursive calls in a divide-and-conquer algorithm need to have a base case so that the algorithm has a point at which it stops dividing and starts conquering. Usually this “bottom out” point is when the recursive method is called on an input of some predefined constant size, such as 1.
Divide-and-conquer algorithms are a little less straightforward in computing an algorithm's order complexity, but their efficiency can be expressed as a recurrence relation. Mergesort can be measured by the number of comparisons based on the input size. This measurment can be expressed as a function that computes the number of comparisons (or “time”) based on the input size n:
T(n) ≤ 2T(n/2) + cn | if n > 2 |
T(2) ≤ c | if n = 2 |
5.2: Further Recurrence Relations
A generalized form of the recurrence relation equation mentioned above is:
T(n) ≤ qT(n/2) + cn | if n > 2 |
T(2) ≤ c | if n = 2 |
where q is the number of subproblems per step in the recursive algorithm. This gives us a few cases depending on what q is…
Case q > 2
Case q = 1
Quadratic Split and Reduce
