SUNY Geneseo Department of Computer Science

Master Theorem, Part 2

Return to List of Lectures

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 (Apan Qasem) interviewing today

• 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

Last applicant (Gahyun Park) interviewing Friday, 2/23

• Student roundtable 2:00 - 2:30, Fraser 208
• Research talk (distributed contention resolution) 2:45, South 340
• Model class (Programmer-defined classes in Java), 4:30, South 340

Questions?

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

Consider how this expands

• Red part contributes a ^log_bn = (b ^log_ba )^log_bn = (b ^log_bn )^log_ba = n^log_ba
• Because a = b ^log_ba

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

... Which really isn't as bad as it looks

Intuition: a f(n/b) term yields behavior of the form n^log_ba.

• If n^log_ba grows faster than g(n), then n^log_ba dominates the closed form
• If n^log_ba and g(n) grow at the same rate, then closed form is slightly larger than n^log_ba
• If n^log_ba grows slower than g(n), then g(n) dominates the closed form

Application: Figure out how n^log_ba relates to g(n) and plug in a, b, and/or g to get a closed form

Try it on the recurrence from the pattern-drawing algorithm

• Recurrence
  • T(n) = 4 T( n/2 ) + 1 if n > limit
  • T(n) = 1 if n <= limit
• Identify parameters
  • a = 4
  • b = 2
  • g(n) = 1
• Plug in
  • n^log_ba = n^log₂4 = n²
• Figure out which case applies
  • 1 = n⁰ = O( n^2-ε )? Yes! ε = 2
  • 1 = n⁰ = Θ(n²)?
  • 1 = n⁰ = Ω( n^2+ε )?
• Plug a, b in to get closed form
  • T(n) = Θ( n^log_ba ) = Θ( n² )

Hand out problem set 8

Lab 5

Hand out

Why you might care about vectors and matrices (done in lab)

Next

(After exam)

Reasoning about loops

Read section 8.1