This is an old revision of the document!
Table of Contents
Chapter 5
- Divide and Conquer: class of algorithmic techniques in which one breaks the input into several parts, solves the problem in each part recursively, and then combines the solutions to these subproblems into an overall solution
- Recurrence Relation: bounds the running time recursively in terms of the running time on smaller instances
- Divide and conquer strategy may reduce the running time to a lower polynomial from the brute-force polynomial time.
5.1 A First Recurrence: The Mergesort Algorithm
- Mergesort: sorts a given list of numbers by first dividing them into two equal halves, sorting each half separately by recursion, and then combining the results of these recursive calls using the linear time algorithm for merging sorted lists
- Base Case: when input has been reduced to size 2, T(n_ is equal to a constant when n is a constant.
- Stop the recursion and sort the two element
- For some constant c, T(n) ⇐ 2T(n/2) + cn when n >2, and T(2) ⇐ c
- To gain an explicit bound, we need to solve the recurrence relation so that T appears only on the left-hand side of the inequality, not the right-hand side as well.
- Approaches to Solving Recurrences
- “unroll” the recursion, accounting for the running time across the first few levels, identifying a pattern that can be continues as the recursion expands. Sum up the running times over all levels → total running time
- Start with a guess, substitute in the recurrence relation, check if it works; Use an argument by induction on n to formally justify this approach
- Unrolling the MergeSort Recurrence
