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.