Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_i [2012/03/06 15:25] – mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_i [2012/03/06 15:49] – mugabej
@@ Line 12: / Line 12: @@
   * It then spends T(n/2) to solve each one since T(n/2) is the worst-case running time for an input of size n/2
   * Finally, it spends O(n) time to combine the solutions from the 2 recursive calls
-  * Thus, the following ** recurrence relation ** is satisfied by the running time:
+  * Thus, the running time satisfies the following ** recurrence relation **:
     * **T(n) ≤ 2T(n/2) + cn** for n >2
     * And T(2) ≤ c
+Thus, 2 is the base case of the recurrence relation in Mergesort algorithm. We assume n is even. To solve for the overall running time of the algorithm, we need to solve the recurrences involved in the algorithm.\\
+\\
+** Approaches to Solving Recurrences **
+There are two general approaches to solving recurrences:\\
+  * **To Unroll the Recurrence **: Account for the running time across the first few levels, and identify a pattern that can be continued as the recursion expands. Then we sum up the running times over all levels of recursion to get the overall running time.
+  * ** To substitute a Solution into the Mergesort Recurrence** : Start with a guess for the solution, substitute it into the recurrence relation, and then check that it works. This approach is formally justified by induction on n.
+===== Unrolling the Mergesort Recurrence =====
+**Analyze the first few levels**:\\
+\\
+>>>>>>>>>>>>>>> At the first level of recursion, we have a single problem of size n. It takes at most cn + time spent in all subsequent recursive calls.\\
+>>>>>>>>>>>>>>> At the next level, we have two problems of size n/2. Each takes at most cn/2 + time spent on subsequent recursive calls, for a total of at most cn.\\
+>>>>>>>>>>>>>>> A the third level, we have 4 problems each of size n/4, each taking time at most cn/4, for a total of at most cn.\\
+\\
+** Identifying the pattern **:\\
+\\
-T(n/2) + T