Differences
This shows you the differences between two versions of the page.
Next revision | Previous revisionNext revisionBoth sides next revision | ||
courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_i [2012/03/06 15:13] – created mugabej | courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_i [2012/03/06 16:16] – [Substituting into the Mergesort Recurrence] mugabej | ||
---|---|---|---|
Line 2: | Line 2: | ||
Divide and conquer algorithms are a class of algorithmic techniques in which one breaks the input into several parts, solves the problem in each part recursively, | Divide and conquer algorithms are a class of algorithmic techniques in which one breaks the input into several parts, solves the problem in each part recursively, | ||
- | Analyzing these problems usually involves solving recurrence relation that bounds the running time recursively in terms of the running time on smaller instances. Mergesort uses the same template as other divide and conquer algorithms to sort a given list of items. | + | Analyzing these problems usually involves solving recurrence relation that bounds the running time recursively in terms of the running time on smaller instances. Mergesort uses the same template as other divide and conquer algorithms to sort a given list of items:\\ |
+ | * Break up problem of size n into two equal parts of size ½n | ||
+ | * Solve two parts recursively | ||
+ | * Combine two solutions into overall solution | ||
+ | \\ | ||
+ | \\ | ||
+ | So, | ||
+ | * Supposing that n is even, the algorithm spends O(n) time to divide the input into two pieces of size n/2 each | ||
+ | * 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 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**: | ||
+ | \\ | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | \\ | ||
+ | ** Identifying the pattern **:\\ | ||
+ | \\ | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | \\ | ||
+ | ** Summing over all levels of recursion **:\\ | ||
+ | \\ | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | \\ | ||
+ | |||
+ | ==== Substituting into the Mergesort Recurrence ==== | ||
+ | |||
+ | |||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>>>>>>>>> | ||
+ | >>>>>>>>>>>>>>> | ||
+ | \\ |