Chapter 5: Divide and Conquer

This chapter will discuss algorithms that break down a given input into different parts and then solves the problem in each part recursively, combining each solution to each part into an overall solution. We will learn how to show and understand these recurrence relations that tell us exactly how that algorithm runs.

This section will discuss Mergesort and the motivations and workings behind it. Mergesort works by dividing the problem into two parts and then solving each, combining each solution at the end. It will take us O(n) time to divide the problem into two, where we will break it down until there is sets of size 2. Then it spends T(n/2) time solving them and finally O(n) to combine everything back into one. So, T(n) is the runtime for the runtime relation.