Divide and conquer

• analyzing involves a “recurrence relation”

• We've seen mergesort before. Basic example for divide and conquer
• divide the input into two pieces of equal size and solve the two subprobles with recursion.
  • basically you continue to divide until you hit the base case.
  • this should give a faster running time then other ways to solve.
• 5.1 - For some constant c, T(n) ⇐ to 2T(n/2) + cn when n > 2 and T(2) ⇐ c
  • this is what a the running time needs to satisfy for a recurrrence relation

Approaches to solving recurrences

• natural way is to “unroll” the recursion. identify a pattern after looking at first few levels and go from there.
• Guess and check for a solution.

Unrolling the mergesort solution

• we did this in class
• see page1 212 - 213
• 5.2 T(n) will be bounded by O(nlogn)

Subsituting into the mergesort recurrence - guess and check

• proof by induction that the running time is right

An approach using partial substitution

• this seems less helpful. the book calls it weaker
• but good if we don't know the exact constants.