SUNY Geneseo Department of Computer Science

Introduction to the Master Theorem

{Date}

CSci 240, Spring 2007
Prof. Doug Baldwin

Return to List of Lectures

Previous Lecture

Misc

Exam 1 Friday (Feb. 23)

Covers material from start of semester through class before exam (e.g., pre- and post-conditions, recursion, induction, recurrences, experiments, etc.)
4 - 6 short-answer questions
- Similar to problem set or lab problems
Full class period (50 minutes)
Open book, open notes, open computer; closed person

Faculty applicant (Alexander Dekhtyar) interviewing today

Student roundtable 11:30 - 12:00, Fraser 208
Research talk (data description for digitized manuscripts) 2:30, Milne 213
Model class (XML data management, databases), 4:30, Welles 123

Next applicant (Apan Qasem) interviewing Wednesday

Student roundtable 11:30 - 12:00, Fraser 208
Research talk (automatically tuning code to architecture) 2:30, Milne 213
Model class (caches) 4:30 - 5:30, Welles 123

Questions?

The Master Theorem

A shortcut for finding asymptotic closed forms for many recurrences that arise in analyzing algorithms.

Motivator / example: the algorithm for drawing rectangular patterns from our first lab

[Rectangles Recursively Inside Rectangles]

        To draw a pattern n pixels on a side
            if n > limit
                draw an n-by-n rectangle
                draw pattern n/2 pixels on a side in upper left
                draw pattern n/2 pixels on a side in upper right
                draw pattern n/2 pixels on a side in lower left
                draw pattern n/2 pixels on a side in lower right
            else
                draw an n-by-n rectangle

What is the execution time of this algorithm, as a function of n?
- How much work in "draw a rectangle"?
  - Assume it's 1 primitive step, make it what the recurrence counts
  - Or sweep it under the rug - count something else, assume "draw" doesn't contribute (asymptotically) to time
  - Both are pretty safe for asymptotic time
- Each recursion divides n by 2 !?
- Recurrence
  - T(n) = 4 T( n/2 ) + 1 if n > limit
  - T(n) = 1 if n <= limit

This recurrence combines 2 common patterns, each leading to a distinctive mathematical behavior in the closed form

f(n) = ... a f(n-1) ...
- f(n) = a f(n-1) = a² f(n-2) = a³ f(n-3)
- General pattern: f(n) is more or less equal to aⁿ
f(n) = ... f( n/b ) ...
- f(n) = ... f( n/b ) ... = ... f( n/b² ) ... = ... f( n/b³ ) ...
- How big can x get before n / b^x is 1?
- i.e., when is n = b^x ?
- x = log_bn
- Recurrences of this form have logarithmic closed forms

The Master Theorem

Let f be defined by a recurrence of the form
- f(n) = Θ(1) in the base case
- f(n) = a f(n/b) + g(n) in the recursive case, b > 1
Then...
- f(n) = Θ( n^log_ba ) if g(n) = O( n^log_ba - ε) for ε > 0
- f(n) = Θ( n^log_ba log n ) if g(n) = Θ( n^log_ba )
- f(n) = Θ( g(n) ) if g(n) = Ω( n^log_ba + ε) for ε > 0 and if a g(n/b) ≤ c g(n) for c < 1 and large enough n

Understanding and using the Master Theorem

Next Lecture