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).

• In ranking systems, we want to be able to count the inversions between two different rankings of the same objects. That is, if we take one list of rankings, we want to tell how many inversions are required to get to the other one.