Chapter 5: Divide and Conquer

Divide and conquer algorithms break the problem into smaller sections, solve those sections, and then put the sections back together. This is done in the hopes that we will be able to reduce the run time of the algorithm.

The Mergesort algorithm splits a list of numbers in half and in half again and then sorts each side and then puts the two halves together. We then designate T(n) to be the worst-case running time of n input. Then for some c T(n) < 2T(n/2)+cn when n>2. This represents the run time of one recurrence relation. We can solve recurrences in two ways: unroll the recursion or guess and check. Unrolling the recurrence means that we analyze the first few levels and at each level, it takes at most cn run time. Then we can find a pattern, and we can sum over this pattern to find the running time. The unrolling method takes O(nlogn) time. Guessing and checking the algorithm, we use a proof by induction to show that T(n) = cnlogn. Since T(n) is the worst case run time, then we can see that the guessing and checking method will also run in O(nlogn). We can also use a partial substitution method that is a little weaker than the other substitution metho but will run in the same time.

We are still going over this is class so it is a little confusing. I also had forgotten what Mergesort was, so this was a good refresher. I'll need to continue to remember things from 112.

I would give this section a 7/10 as it was helpful but a little confusing for me.