This is an old revision of the document!
definition:P234 Divide and conquer refers to a class of algorithmic techniques in which one breaks the input into several parts, solves the problem ifi each part recursively, and then combines the solutions to these subproblems into an overall solution
important concept
recurrence relation that bounds the running time recursively in terms of the running time on smaller instance.
5.1 A First Recurrence: The Mergesort Algorithm
Summary Divide-and-conquer process
- Break up problem into several parts
- Solve each part recursively
- Combine solutions to sub-problems into overall solution
Mergesort recurrence relation: T(n) < 2T(n/2) + cn
Solving Recurrences: two methods
unroll the recurrence:
- Look for patterns in runtime at each level
- Sum up running times over all levels
Substitute guess solution into recurrence:
* Check that it works
- Induction on n
