Chapter 5

Divide & Conquer notes

• Divide & conquer algorithms are characterized by the fact that they divide the input into smaller groups and solve the problem recursively.
• They're often used to get polytime to a lower polynomial.
• Mergesort is a D&C algorithm.
  • We divide the list to be sorted into smaller lists and sort each at the base level, then merges sorted lists.

• When there are more than two subproblems
  • For the first few levels, we have a problem of size n taking cn plus the recursive call time.
  • At the next level, we have q problems of size n/2, taking time cn/2 plus the recursive call times.
  • At the next level, we have q^2 problems of size n/4, taking time q^2*cn/4 time.
  • Thus we'll always have q^j distinct instances at level j, of size n/(2^j). Thus at level j we have time q^j(cn/(2^j).
  • After a lot of math, we get the important thing, which is that T(n)≤O(n^(log_2(q)).
    • If we apply partial substitution, we also get the same result.
• What if there's only one subproblem?
  • At level j we have one instance of size n/(2^j) and adds cn/(2^j) to the runtime, which converges as a sum to T(n) ≤ 2cn = O(n).
• Finally, for T(n) ≤ 2T(n/2) + O(n^2)
  • After some work (p 220, 221), we find that T(n) ≤ O(n^2).