For a divide and conquer algorithm, we break the input into several parts and solve each part recursively. We then combine all solutions into an overall solution. To figure out the running time of a divide and conquer algorithm, we look at the recurrence relation, which is based on the number of times we recursively call the algorithm. Generally for a divide and conquer algorithm, the brute force method will run in some polynomial time, and the divide and conquer method will reduce that time to a lower polynomial.

Readability: 8/10

Mergesort is a method used to sort two lists of values. We divide the list in half and sort each half using recursion, and finally we combine the results in linear time. We get the recurrence relation T(n) ≤ 2T(n/2)+cn for n>2, and T(2)≤c for the base case. There are two ways to solve the recurrence, unrolling the algorithm or starting with a guess. Unrolling the recursion involves looking at the running time for the first levels until we see a pattern. Starting with a guess and substituting, we use induction to find the solution. Also, a “partial” substitution can be used, where we leave our constants as variables and try to figure them out later.

Readability: 5/10 because of the difficult math

We can generalize the problem from section 5.1 by changing the number of recursive calls to a variable q instead of 2. Our recurrence relation then becomes T(n)≤qT(n/2)+cn for n>2 and T(2)≤c. The recurrence relation can be solved using unrolling or substitution. For the case where q>2, we find that each level requires more work than the previous level. This is unlike the case where q=2, where every level requires the same amount of work. With q>2, we get an efficiency of O(n^log₂q). For the case where q=1, we find that the first level performs half of the work, and each subsequent level performs half the work of the one before it. For the case of q=1, we get O(n) efficiency. If the merging of our recursively found results takes quadratic instead of linear time, we get O(n²).

Readability: 5/10