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

Binary Search

• Analyzing the algorithm
  • Instead of recursively solving 2 problems, solve q problems
    • Size of problems is still n/2
  • Combining solutions is still O(n)
  • Recurrence relation:
    • For some constant c, T(n) ≤ qT(n/2) + cn when n > 2 and T(2) < c
• Unroll the recurrence
  • T(n) = T(n/2) + c
    • Constant work at each level
    • Number of levels = log n
    • So the runtime is O(log n)
  • The case of q > 2
    • First level: qT(n/2) + cn
    • Next level: qT(n/4) + c(n/2)
    • qk problems at level k
    • size: n/2^k
    • Number of levels: log n
      • Each level takes q^k * c * (n/2^k) = (q/2)icn
    • Overall run time: O(n^{log q})