Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
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 22:23] (current) – 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 | * 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 | * 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 |
* **T(n) ≤ 2T(n/2) + cn** for n >2 | * **T(n) ≤ 2T(n/2) + cn** for n >2 | ||
* And T(2) ≤ c | * 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**:\\ | ||
+ | \\ | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | \\ | ||
+ | ** Identifying the pattern **:\\ | ||
+ | \\ | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | \\ | ||
+ | ** Summing over all levels of recursion **:\\ | ||
+ | \\ | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | \\ | ||
+ | |||
+ | ==== Substituting into the Mergesort Recurrence ==== | ||
+ | |||
+ | |||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | \\ | ||
+ | ** An Approach Using Partial Substitution**: | ||
+ | \\ | ||
+ | With this approach: | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | \\ | ||
+ | As useful as it is, our this section was really short and straightforward. I give a 9/10. | ||
+ | |||
+ | |||
- | T(n/2) + T |