- Section 4.6
- Statement of theorem?
- Informally, it gives an asymptotic closed form for recurrences of the form T(n) = a T(n/b) + f(n)
- The behavior of T is dominated either by an nlogba term arising from the recursion, or by f(n), according to how big (asymptotically) f is compared to nlogba
- Why floor/ceiling in theorem? Notation?
- Uses in theorem statement acknowledge that T is only defined on natural numbers, so references to n/b are short-hands for floor or ceiling of n/b
- Applicable to multiple sub-problem sizes?
- No, theorem is about T(n) = a T(n/b), doesn’t allow for anything other than n/b as sub-problem size
- Statement of theorem?
- Do sums work the same for n not exact power of b?
- Yes, once certain asymptotic approximations are established
- Overview of proof structure
- Part 1: theorem holds if n = bk for natural number k
- Lemma 4.2 - T(n) = Θ(nlogba) + sum
- Lemma 4.3 - closed forms for sum
- Lemma 4.4 - combine 4.2 and 4.3 to prove Master Theorem
- Part 2: adapt part 1 for general n
- Consider how “adapting” works for third case in Lemma 4.3
- Consider how “adapting” works for third case in Lemma 4.3
- Part 1: theorem holds if n = bk for natural number k
- Using the Master method
- Read Section 4.5