This is an old revision of the document!
Table of Contents
Chapter 5
5.1 Mergesort
Mergesort's behavior can be described as dividing the input into two halves, solving each half separately by recursion, and then combining the two results into an overall solution. So, it takes O(n) time dividing the input in half, T(n/2) time to solve each half, then O(n) time to combine the two solutions back together. Thus, the recurrence relation is 2T(n/2) + O(n). This itself is not a run time, however. In order to determine the run time of an algorithm from a recurrence, we can either “unroll” the recurrence or simply guess. In the case of Mergesort, the run time is O(nlogn). The overall readability of this section was 6/10.
