Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revisionNext revisionBoth sides next revision | ||
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 16:14] – [Unrolling the Mergesort Recurrence] 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. | * ** 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**:\\ | ||
+ | \\ | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | \\ | ||
+ | ** Identifying the pattern **:\\ | ||
+ | \\ | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | \\ | ||
+ | ** Summing over all levels of recursion **:\\ | ||
+ | \\ | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | \\ | ||
+ | ==== Substituting into the Mergesort Recurrence ==== | ||
+ | |||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>>>>>>>>> |