Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_i [2012/03/06 15:42] – mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_i [2012/03/06 15:49] – mugabej
@@ Line 23: / Line 23: @@
   * ** 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 **:\\
+\\