SUNY Geneseo Department of Mathematics

Using the Master Theorem

Thursday, October 8

Math 303
Fall 2015
Prof. Doug Baldwin

Misc
- Exam 1
  - Tuesday Oct. 20
  - Could move to Thursday Oct. 15 - no
  - Time and correctness analysis of algorithms
  - 4 - 6 short-answer questions
  - I’ll try to provide practice questions after break
  - Open book, notes, computer; closed person
Questions?
Using the Master Theorem
- Section 4.5
  - Process
    - Identiify a, b, f(n)
    - Compare f(n) to n^log_ba
    - Apply corresponding part of Master Theorem to get asymptotic closed form
  - Beware special cases, gaps, esp. case 3
- Examples
  - T(n) = 8 T(n/4) + n
    - a = 8
    - b = 4
    - f(n) = n
    - n^log_ba
      - log₄8 = 3/2
      - n^log_ba = n^3/2
    - f(n) = n in O( n^3/2-ε ) for ε ≤ 1/2
    - T(n) = Θ( n^3/2 )
  - T(n) = 8 T(n/4) + n²
  - T(n) = 8 T(n/4) + n^3/2
  - Divide-and-conquer matrix multiplication
    - Idea: multiply square matrices by recursively multiplying sub-matrices and adding results
    - See algorithm on page 77 of textbook
    - In its base case, this algorithm does a constant amount of work
    - In its recursive case, this algorithm does…
      - 8 recursive multiplications
      - Plus Θ(n²) time to add results
    - So recurrence relation for running time is
      - T(1) = 1
      - T(n) = 8 T(n/2) + n², n > 1
- Problem set
Next
- Mini-assignment: Find asymptotic closed form for matrix multiplication recurrence
- Lower bounds for problems
  - No reading