Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2014:journals:emily:entrysix [2014/03/05 02:23] – [Chapter 4.8] hardye
+++ courses:cs211:winter2014:journals:emily:entrysix [2014/03/05 02:49] (current) – [Chapter 5.1] hardye
@@ Line 135: / Line 135: @@
 **(5.1)** For some constant c, T(n) =< 2T(n/2) + cn when n > 2 and T(2) =< c.
+T(n) is bounded by an inequality. There is a base case that says T(n) is equal to a constant when n is a constant. We have to solve the recurrence so that T is only on the LHS of the inequality.
+How to solve recurrences:
+  * "unroll" the recursion by accounting for the run time in the first few levels then specify a pattern for as the recursion expands. Sum the runtimes over all levels
+  * start with a guess and check if it works by substituting it into the recursion. Justify by induction!
+**Unrolling the Mergesort Recurrence**
+  * level 1: problem size n, takes cn time
+  * level 2: two problems size n/2 each takes cn/2 time for a total of at most cn
+  * level 3: four problems size n/4 each take cn/4 time for  total of at most cn
+  * pattern: at level j of the recursion the number of subproblems is 2<sup>j</sup> with size n/2<sup>j</sup> so takes at most cn/2<sup>j</sup> time
+  * sum over all levels: number of times the input is halved is log n so the sum of the cn work on log n levels is O(n log n)
+**Substituting a Solution into the Mergesort Recurrence**
+I would rate this chapter a readability of 8/10. It was fairly short and easy to follow but if I hadn't read this chapter after it was presented in class I would have been a little lost.