CS211: Design and Analysis of Algorithms

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
Mergesort sorts a given list of numbers by first dividing them into two equal halves, sorting each half recursively, and then combining the two results. Basically, divide the list of numbers, solve and merge(conquer) both of them after sorting. We need a base case for the solution, which is in this case, when the length of the list is 2, compare the two elements , and sort them. Suppose n is even and T(n) is the time spent on such an instance, the algorithm spends O(n) time to divide the input into two pieces of size n/2. Thus satisfying a recurrence relation on //page 211//. A recurrence relation will determine the running time. There are two basic ways on solving a recurrence:
  * Unrolling the recurrence, account for the run time for the first levels, and identify a pattern. 
  * Or start with a guess and check if it works.
**Unrolling the Mergesort Recurrence**.
  * Analyzing the first few steps: We have a problem that takes c*n/level time for a total of at most cn time.
  * Identify a pattern: Time taken at each level is cn/2^j, j being the level.
  * Summing over all levels of recursion: we have log n recursions overall, which gives us an overall time of O(n logn) when n>1.
We simply guess that the running time is correct by simply plugging it in the recurrence relation. We can also use the substitution method to get the constant hidden in the upper bound, this is in detail on //page 214//.

This section was short and pretty easy to understand, thus a scale of 9/10.