Divide and Conquer Algorithms

• Process
  • Break up problem into several parts
  • Solve each part recursively
  • Combine solutions to sub-problems into overall solution
  • Use recurrences to analyze the runtime of divide and conquer algorithms
• Approaches to Solving Recurrences
  • Unroll recursion
    • Look for patterns in runtime at each level
    • Sum up running times over all levels
  • Substitute guess solution into recurrence
    • Check to make sure it works
    • Prove that it works using induction on n

Merge Sort

• Analyzing Merge Sort
  • General Template:
    • Break up problem of size n into two equal parts of size 1/2n → O(1)
    • Solve two parts recursively → T(n/2) + T(n/2)
    • Combine two solutions into overall solution → O(n)
  • Definition: T(n) = the number of comparisons to merge sort an input of size n
    • Recurrence relation: T(n) = 2T(n/2) + O(n)
      • T(n) =T(n/2) + c
    • Cost of each level in the tree is c*n
      • log n levels
    • Run time = log n